arrays - 检查 Array 是否按 Log(N) 排序

Question

我听说可以使用一些分而治之的算法来检查数组是否在 Log(N) 中排序。我知道的最快方法是 O(N) （只需遍历列表并检查元素是否大于前一个）。

我在网上查了一下，什么都找不到，但我想在放弃之前在这里问问有没有人知道。

Answer 1

要检查数组是否在没有先前知识的情况下排序，您需要至少查看所有元素一次，因此 O(n) 是最小值。

Answer 2

不可能的。您必须查看每个元素。