0

Big Oh 是如何计算排序算法的？我编写了一个程序来使用选择排序、合并排序和插入排序对一副纸牌 (n = 52) 进行排序。对于每种排序算法，我必须计算计算成本。我该怎么做？

现在我可以诚实地承认这是我家庭作业的一部分，但我只是在寻求一些帮助。我是 Big Oh 符号的新手，浏览了几个网站，但在排序算法方面无法弄清楚。

至少有人可以给我提示吗？

我刚刚参考了维基百科的选择排序、插入排序和合并排序。

插入排序：最佳情况：O(n)，最坏情况和平均情况：O(n^2)

选择排序：所有三种情况的 O(n^2)

合并排序：所有三种情况的 O(nlog n)

真的吗？

4

1 回答 1

2

您正在寻找的东西称为复杂性，在您的情况下可能是在运行时方面。“大 O” 只代表上边界，而“小 o” 代表下边界，平均值是“Theta”。它们表示用于执行程序的时间步长的函数，与缩放和加法无关。

示例：如果您的排序算法对每个列表（大小为 n）的项目进行一次迭代（例如，使用 for 循环）并且在每一步上再次循环（在那里执行 l 步），那么您将需要大约 l*n*n 步再加上一些 k 步以进行准备等。这将导致复杂度为O(l*n*n + k)，等于O(n*n) = O(n^2)，因为 l 和 k 是常数。

更多更深入的信息：http ://en.wikipedia.org/wiki/Time_complexity

于 2013-02-12T22:39:19.913 回答