时间复杂度类似于冒泡排序。

Question

分析以下排序算法：

      for (int i = 0; i < SIZE; i++)
      {
        if (list[i] > list[i + 1])
       {
           swap list[i] with list[i + 1];
           i = 0;
       }
     }

我想确定这个算法的时间复杂度，在最坏情况下...我不理解为什么它是O(n^3)。

- user2809437

---

这不是完整的冒泡排序，需要另一个循环。而冒泡排序的时间复杂度是 O(n^2)，而不是 3。 - Hanky Panky

谢谢马克，很有道理。忽略了那个。 - Hanky Panky

只是提醒一下，你的算法有一个错误。你应该使用for (int i = 0; i < SIZE - 1; i++)，否则当你尝试与list[i+1]进行比较时，会出现索引错误。 - Shashank

放松一下..这只是伪代码.. - user1064590

@VirtualBaseClass，也许你从未听说过Bogosort？ - Mark Ransom

Answer 1

我对n = 10和n = 100进行了分析。比较的次数似乎是O(n³)，这是有道理的，因为i平均被设置为0 n / 2次，所以它大约需要n² *（n/2）次比较和递增运算来完成for循环，但交换的次数似乎只有O(n²)，因为显然不需要更多的交换来对整个列表进行排序。最好情况下，当然是n-1次比较和0次交换。

对于最佳情况测试，我使用已经排序的n个元素的数组：[0...n-1]。

对于最坏情况测试，我使用一个反向排序的n个元素数组：[n-1...0]

def analyzeSlowSort(A):
    comparison_count = swap_count = i = 0
    while i < len(A) - 1:
        comparison_count += 1
        if A[i] > A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            swap_count += 1
            i = 0
        i += 1
    return comparison_count, swap_count

n = 10
# Best case
print analyzeSlowSort(range(n)) # ->(9, 0)
# Worst case
print analyzeSlowSort(range(n, 0, -1)) # ->(129, 37)
n = 100
# Best case
print analyzeSlowSort(range(n)) # ->(99, 0)
# Worst case
print analyzeSlowSort(range(n, 0, -1)) # ->(161799, 4852)

显然，这是一种在比较方面非常低效的排序算法。:)

- Shashank

Answer 2

好的.. 开始吧.. 在最坏的情况下，假设我们有一个完全翻转的数组..

9 8 7 6 5 4 3 2 1 0

每次交换时.. i 都会被重置为0。

让我们从翻转 9 8 开始：现在我们有了 8 9 7 6 5 4 3 2 1 0，i 被重置为零。

现在循环运行到2，我们再次翻转.. : 8 7 9 6 5 4 3 2 1 0 i 再次重置.. 但是要把 7 放到第一位，我们需要再翻转 8 和 7：7 8 9 6 5 4 3 2 1 0

所以循环次数如下：

T(1) = O(1) T(2) = O(1 + 2) T(3) = O(1 + 2 + 3) T(4) = O(1 + 2 + 3 + 4) 等等..

最后，对于在此情况下最大的第n项，其T(n) = O(n(n-1)/2)。

但是，对于整个内容，您需要将所有这些项相加， 这可以通过Summation of (T(n)) = O(Summation of (n^2)) = O(n^3)来限制。

附加说明： 这样想：对于每个元素，您需要上升并将其带回...但当您将其带回时，它只有一个空格。我希望这能让它更清楚一些。 另一个编辑 如果以上内容有任何不清楚的地方，请这样考虑：您必须将0带到数组的前面。您最初需要走9步到达零，并将其放在1之前。但是之后您会被魔法传送（i = 0）到数组的开头。因此，现在您必须走8步到达零，然后将其放在两个位置。再次Zap！并且您回到数组的开头。每次需要走多少步才能使零正好在最前面。 9 + 8 + 7 + 6 + 5 + .. 这是递归的最后一项，因此受到数组长度的平方的限制。这有意义吗？现在，对于每个元素，您平均执行O（n）的工作..对吧？这相当于将所有术语相加..我们有O（n ^ 3）。

如果有帮助或不清楚的事情，请评论。

- user1064590

Answer 3

很明显，仅使用for循环的时间复杂度为O(n)。问题是，它会运行多少次？

每当进行一次交换时，循环就会重新开始。你将会为每个元素从其起始位置到达其在排序后的正确位置进行一次交换。对于一个反向排序的输入，这将平均进行n/2次交换，再加上每个元素的交换次数，得到另一个O(n)。这就是导致O(n^3)的原因。

- Mark Ransom