最坏情况下的时间复杂度为这个愚蠢的排序？ [英] Worst case time complexity for this stupid sort?

问题描述

在code是这样的：

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）？

After trying out a few things i figure the worst case is when the input array is in descending order. Then looks like the compares will be maximum and hence we will consider only compares. Then it seems it would be a sum of sums, i.e sum of ... {1+2+3+...+(n-1)}+{1+2+3+...+(n-2)}+{1+2+3+...+(n-3)}+ .... + 1 if so what would be O(n) ?

如果我不是在正确的道路上能有人指出哪些为O（n）是和它如何得出？干杯！

If I am not on the right path can someone point out what O(n) would be and how can it be derived? cheers!

推荐答案

对于初学者来说，总和

（1 + 2 + 3 + ... + N）+（1 + 2 + 3 + ... + N - 1）+ ... + 1

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

实际上不是为O（n）。相反，它是为O（n ³ ）。你可以看到这一点，因为总和1 + 2 + ... + N = O（N ² ，并且有n他们每个人的副本，您可以更正确地表明，这种求和是与西塔。 （正 ³ ）通过查看第一n / 2这些术语的每一个这些术语的至少是1 + 2 + 3 + ... + N / 2 =＆的Theta;（正 ² ），所以有n个东西是与西塔/ 2份;（N ² ），给人一种紧约束的和西塔（N ³ ）

is not actually O(n). Instead, it's O(n³). You can see this because the sum 1 + 2 + ... + n = O(n², and there are n copies of each of them. You can more properly show that this summation is Θ(n³) by looking at the first n / 2 of these terms. Each of those terms is at least 1 + 2 + 3 + ... + n / 2 = Θ(n²), so there are n / 2 copies of something that's Θ(n²), giving a tight bound of Θ(n³).

我们可以上界，该算法的总运行时间在为O（n ³ ），他指出，每一个交换减少阵列中的反转的一个数目（反转是一对元素的出来的地方）。可以有最多为O（n ² ）在一个数组倒置和排序后的数组中有没有倒（你知道为什么吗？），所以有至多为O（n ² ）越过数组，每个花费最多O（n）的工作。它们共同提供了一个界为O（n ³ ）。

We can upper-bound the total runtime of this algorithm at O(n³) by noting that every swap decreases the number of inversions in the array by one (an inversion is a pair of elements out of place). There can be at most O(n²) inversions in an array and a sorted array has no inversions in it (do you see why?), so there are at most O(n²) passes over the array and each takes at most O(n) work. That collectively gives a bound of O(n³).

因此​​，与西塔（N ³ ）你已经​​确定最差情况下的运行时间是渐近紧，所以算法的时间为O（N ³ ）和有最坏情况运行时和西塔。（N ³ ）

Therefore, the Θ(n³) worst-case runtime you've identified is asymptotically tight, so the algorithm runs in time O(n³) and has worst-case runtime Θ(n³).

希望这有助于！

这篇关于最坏情况下的时间复杂度为这个愚蠢的排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！