使用 O(1) 检查数组是否已排序

Question

是否可以以最差的时间复杂度检查（在Java中）数组是否已排序O(1)？

Answer 1

不可能有比O(n)复杂性更好的正确算法。我们用反证法来证明一下。如果我们给出一个比O(n) 复杂性更好的算法，我们可以提供一个测试数组

{1, 2, 3, ..., n}

其中n足够大，因此算法必须跳过一些项目（请注意，如果算法检查所有项目，则它至少具有O(n)时间复杂度）。如果算法返回false则不正确；如果它返回，true我们必须再创建一个测试。设m为未检查的项目：

{1, 2, 3, ... m - 1, m, m + 1,... n}
                     ^
Not inspected by the algorithm.

让我们像以前一样创建测试数组，但更改m为n + 1(或1if m == n)

{1, 2, 3, ..., m - 1, n + 1, m + 1, ... n}
                        ^
           we changed m into n + 1 

由于m没有检查，算法返回的结果true现在是不正确的。所以时间复杂度优于的任意算法都是O(n)不正确的，或者换句话说：不存在优于O(n)时间复杂度的正确算法。