如果选择排序和冒泡排序算法的代价都是O（N2），那么为什么我的代码中没有反映出这一点呢？

Question

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

我将我的代码与同行的代码进行了比较，它似乎不是由函数本身引起的，尽管我没有排除这种可能性

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

我希望输出比选择排序高一点，但实际上要高得多

Answer 1

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

代码段A:

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次；然而，考虑到操作有O(1)，这三个代码段的时间复杂度都是O(N^2)，但是运行它们显然不会花费相同的时间

有关更多信息，请参阅这个信息丰富的video