对 1 000 000 个整数的数组进行冒泡排序需要多长时间？

Question

冒泡排序的计算复杂度为 O(n^2)。那么，如果我们的 CPU 为 3.5 GHz，这些计算结果是否正确？ 1 000 000 * 1 000 000 =10^12 3.5 GHz 每个麦克风约 6 000 000 个（我认为是这样，如果这不是真的，请纠正我）

(10^12/6 * 10^6)/60=~2777 小时 这是真的吗？

Answer 1

我认为你误解了 BigO 表示法。

在理论信息学中，我们使用 BigO 来表达上限和下限，因此这并不意味着您只需插入该值并找到一些时间。如果您不知道 BigO 表示法 O(10N) = O(N)。

例如，看一下快速排序的复杂性，使用波形符表示法时，它是 ~1.39NlogN，使用 BigO 时，它是 O(NlogN)。

BigO 或波形符号与毫秒无关。然而，了解时间的唯一方法是使用比率测试。

BigO 用于表示比较次数。

Answer 2

事实并非如此。在普通计算机上使用 C++ 大约需要一个小时。尝试使用不同的输入值进行基准测试，并记住，当您将整数数量加倍时，计算时间应增加四倍。

Answer 3

如今的台式电脑可以在大约 5 秒内完成十亿 (10⁹) 个小事情。

对 10⁶ 随机整数进行冒泡排序需要大约 10¹² 的小事情，或者大约 5000 秒 = 83 分钟。

无论如何，这可能会相差 4 倍左右。 你必须用一种编译良好的语言来编写它才能得到这个时间，因为 C++ 中的“小东西”在 JavaScript 中要大得多。

Answer 4

Big-O 表示法在回答“随着问题规模的增大，解决问题所需的时间/内存如何增长？”这一问题时很有用。它故意忽略所有“小”细节，并认为算法 A 使用比另一个算法 B 多 10 倍（或 100000 倍 - 任何常数比率）的时间是等效的。当然，在现实生活中，10 倍性能确实很重要。所以第一个问题是 O(n^2) 忽略所有常数因子（但现实世界时间不会）。

使用（当前第一个伪代码示例）维基百科版本的冒泡排序：

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        swapped := false
        for i := 1 to n - 1 inclusive do
            if A[i - 1] > A[i] then
                swap(A[i - 1], A[i])
                swapped = true
            end if
        end for
        n := n - 1
    until not swapped
end procedure

你可以看到，如果所有元素都初始排序的话，将会有 0 次交换。任何实现此伪代码的现代计算机都能够在不到 1 秒的时间内对已排序的 1M 整数数组进行“排序”。所以第二个问题是（大多数实现，包括上面的）如果数组几乎是有序的，冒泡排序会快得多。碰巧的是，在现实生活中，数组比随机采样所期望的更加有序——这导致了现实世界的排序算法寻找捷径来利用这一点。

当然，第三个问题（在查看了 big-O 忽略的代码以及数组中的确切无序程度之后）与执行代码的平台的详细特征有关，以及您在该平台上执行的具体机器级指令。例如，如果所有数据都适合机器的缓存（从而避免昂贵的重复访问主内存），则可以获得进一步的效率 - 在很大程度上独立于算法的实现的水平。

如果您查看真实世界基准测试，它们会详细说明所有 3 个方面：使用的精确代码、精确的数据输入以及精确的编译器和机器架构。请注意，即使如此，随着程序大小的增加，预测运行时间将如何增加也不容易，因为由于数据不再适合较慢的内存，许多转换将以steps的形式出现，而不是平滑的增加。

TLDR：唯一安全的估计是测量时间。它只会回答您的实施、选择的输入和机器的问题。如果做不到这一点，您可以进行几次较小的运行，将抛物线拟合到您的数据，并将结果推断为 1M 大小：它不会偏离目标太远，因为 1M 整数并没有那么多。