这是我的代码:
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
对我来说很明显,我的代码或我对算法时间复杂度的理解完全被磨损了。可能两者都有。你们中的任何好心人能解释一下我做错了什么吗?
返回适当的操作量(时间复杂度)。
运行程序所获得的操作数量并不等于其时间复杂度。时间复杂度是从分析得出的,它证明对于所有足够大的 𝑛 值,操作数量受 𝑛 函数限制。
最好情况...最坏情况:比较次数 = 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上找到更多相关信息。