时间戳

首页 > 解决方案 > 如果选择排序和冒泡排序算法的成本都是 O(N2) 那么为什么这没有反映在我的代码中？

python - 如果选择排序和冒泡排序算法的成本都是 O(N2) 那么为什么这没有反映在我的代码中？

问题描述

在我的程序中，我试图比较冒泡排序和选择排序算法，但是在比较结果时，冒泡排序需要大约 10 秒才能对 10000 个随机数组进行排序，而选择排序需要 2 个。

我已经将我的代码与同行的代码进行了比较，它似乎不是由函数本身引起的，尽管我没有排除它。

完整程序链接在这里：https ://drive.google.com/file/d/1sfOZN_lLBeSmtZJpzmpVjCr5JOeHD9V0/view?usp=sharing

我希望输出比选择排序高一点，但它要高得多。

标签： pythonsortingbubble-sortselection-sort

解决方案

大 O 符号不等同于时间。它是时间复杂度的度量。以以下片段为例：

片段一：

for i in range(n):
   for j in range(n):
      # operation

片段 B：

for i in range(n):
   for j in range(n):
      # operation
   for k in range(n):
      # operation
   for q in range(n):
      # operation

片段 C：

for i in range(n):
   for j in range(n):
      # operation
   for k in range(n):
      # operation
for q in range(100):
   # operation

在片段 A 中，操作将是运行N^2时间，在片段 B 中，操作将是运行3N^2时间，而在最后一个片段中，它将运行2N^2+100时间；然而，考虑到 operation has O(1)，所有三个片段的时间复杂度都为 ，O(N^2)但很明显，运行它们不会花费相同的时间。

观看此内容丰富的视频以获取更多信息。

推荐阅读