如何在Python中的冒泡排序算法中正确计算操作（时间复杂度）

Question

这是我的代码：

def sort_bubble(list):
    comp_counter = 0
    swap_counter = 0
    n = len(list)
    for i in range(n-1):
        for j in range(n-i-1):
            comp_counter += 1
            if list[j] > list[j+1]:
                swap_counter += 1
                list[j], list[j+1] = list[j+1], list[j]
    return comp_counter, swap_counter

它需要对一个列表进行冒泡排序，然后返回适当数量的操作（时间复杂度）。

我在两种情况下运行了此代码（每个列表有 20000 个整数）：

a) 对已经排序的列表进行排序（最佳情况）：比较次数 = 49995000 = n(n-1)/2; 交换次数 = 0。在我看来，这里有些问题，因为最好情况下的比较次数应该是 O(n) ，交换次数应该是 O(1) （对于冒泡排序算法）。

b) 对“向后”排序列表进行排序（最坏情况）：比较次数 = 49995000 = n(n-1)/2; 互换数量= 49993762。在最坏的情况下，该算法应该有 O(n^2) 交换和 O(n^2) 比较。同时交换和比较的次数更接近 O(n^2)/2

对我来说很明显，我的代码或我对算法时间复杂度的理解完全被磨损了。可能两者都有。你们中的任何好心人能解释一下我做错了什么吗？

Answer 1

返回适当的操作量（时间复杂度）。

运行程序所获得的操作数量并不等于其时间复杂度。时间复杂度是从分析得出的，它证明对于所有足够大的 𝑛 值，操作数量受 𝑛 函数限制。

最好情况...最坏情况：比较次数 = 49995000 = n(n-1)/2

比较计数器的增加方式不依赖于输入列表的内容。它的最终值仅取决于𝑛。因此，不存在最好或最坏的情况。最终结果总是 𝑛(𝑛−1)/2。

如果您期望看到差异，那么这意味着您应该实现一个冒泡排序版本，该版本可以检测输入列表是否已排序并且可以提前退出。另请参阅维基百科上的 冒泡排序，以及在一个版本中如何使用

swapped

布尔变量，以及在另一个版本中

n

和

newn

。后一个版本在外循环的给定迭代中标识最后一次交换发生的位置，并得出结论：从该索引开始的所有值都处于其最终的排序位置，不需要再次比较。

不相关，但不要调用您的列表

list

，因为这是本机 Python 函数的名称。

以下是如何调整您的代码：

def sort_bubble(lst):
    comp_counter = 0
    swap_counter = 0
    n = len(lst)
    sorted_from = n
    while sorted_from > 0:
        last_swap_index = 0
        for j in range(sorted_from - 1):
            comp_counter += 1
            if lst[j] > lst[j+1]:
                swap_counter += 1
                lst[j], lst[j+1] = lst[j+1], lst[j]
                last_swap_index = j + 1
        sorted_from = last_swap_index
    return comp_counter, swap_counter

对于最好的情况，您现在将获得尽可能少的比较次数。

时间复杂度

时间复杂度是从分析中得到的。这里我们可以证明，最好情况下的比较次数为 θ(𝑛)，最坏情况下的比较次数为 θ(𝑛²)。交换次数的最佳情况为 θ(1)，最坏情况为 θ(𝑛²)。

同时交换和比较的次数更接近 O(n^2)/2

这证实了对时间复杂度的误解。 O(𝑛²)/2——或更准确地说，O(𝑛²/2)——与 O(𝑛²) 相同。您可以在维基百科的Big O notation上找到更多相关信息。