这种愚蠢的排序最糟糕的时间复杂性？

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 ³)的界限.

因此,您已识别的Θ(n ³)最坏情况运行时渐近紧,因此算法在时间O(n ³)内运行并且具有最坏情况运行时间Θ(n ³).

希望这可以帮助!

Answer 2

它每次交换执行一次列表迭代.必要的最大交换次数是O(n * n)反向列表.每次迭代都是O(n).

因此算法是O(n * n * n).