algorithm - 这种愚蠢的最坏情况下的时间复杂度？

Question

代码如下:

for (int i = 1; i < N; i++) {
    if (a[i] < a[i-1]) {
        swap(i, i-1);
        i = 0;
    }
}

在尝试了一些事情之后，我认为最坏的情况是输入数组按降序排列。然后看起来比较将是最大的，因此我们将只考虑比较。那么它似乎是总和，即... {1+2+3+...+(n-1)}+{1+2+3+...+(n-2 )}+{1+2+3+...+(n-3)}+ .... + 1 如果是的话 O(n) 是多少？

如果我不在正确的道路上，有人可以指出 O(n) 是什么以及它是如何推导出来的吗？干杯!

Answer 1

对于初学者来说，总结

(1 + 2 + 3 + ... + n) + (1 + 2 + 3 + ... + n - 1) + ... + 1

实际上不是 O(n)。相反，它是 O(n³)。你可以看到这一点，因为总和 1 + 2 + ... + n = O(n²，并且每个都有 n 个副本。你可以更恰本地证明这个总和是 Θ( n³) 通过查看这些项的前 n/2。这些项中的每一项至少为 1 + 2 + 3 + ... + n/2 = Θ(n² )，所以有 n/2 个 Θ(n²) 的副本，给出了 Θ(n³) 的紧界。

我们可以将此算法的总运行时间上限设置为 O(n³)，注意每次交换都会将数组中的反转次数减少一个(反转 是一对不合适的元素)。数组中最多可以有 O(n²) 次反转，而排序数组中没有反转(你知道为什么吗？)，所以最多有 O(n² ) 遍历数组，每个最多需要 O(n) 的工作。这共同给出了 O(n³) 的界限。

因此，您确定的 Θ(n³) 最坏情况运行时间是渐近紧的，因此该算法的运行时间为 O(n³) 并且具有最坏情况运行时 Θ(n³).

希望这对您有所帮助!