真的很困惑时间复杂

Question

我知道如何计算每个算法的bigO，一般来说，它是如何工作的。例如，在链表中找到一个特定的数字就是O（N），因为你可能需要从头到尾遍历链表中的每个输入。然而，bigO实际上对于时间意味着什么？即使插入排序具有更快的“时间复杂度”，合并排序的运行速度还是可以比插入排序快吗？请给我你的意见，所以我可以理解。非常感谢你。

Answer 1

有一个看看这个例子：

比方说你有两个算法A₁和A₂。这样做，但第一个复杂度为Θ(n)，第二个复杂度为Θ(n²)。两种算法都有不同的运行时间。您无法从复杂性中计算运行时间，因为它取决于具体的实现方式，运行的计算机，复杂性和其他方面无法看到的东西。但是，您可以通过复杂性预测运行时间的变化。 假设您将输入从长度n更改为长度2n，表示您将输入长度加倍。那么运行时间也应该（几乎）为A₁的两倍，但它应该是A₂以上的约4倍，因为(2n)² = 4n²。

要解决插入排序与合并排序示例： 插入排序的复杂性为O(n²)，合并排序的复杂度为O(n log n)。所以合并排序比插入排序有更好的复杂性，并且运行速度也应该更快。可能（对于非常短的列表）插入排序运行速度比合并排序快，因为合并排序有一个更大的常数因子隐藏在大O符号中。

Answer 2

您遇到的问题/问题在初学者级别非常普遍。我建议你阅读更多有关“渐近符号”的内容（网络上有很多有用的视频和网站可以解释这一点）渐近分析正在考虑将算法应用于大型数据库时的性能。 渐近概念基本上是三种类型 -

1. 大O
2. 大欧米茄
3. 西塔的时候，我们有一个渐近上限

大O使用，这是 大当存在正的常数c和n时，g（n）的O等于f（n）{O（g（n））= f（n）}，使得 = f（n）< = cg ）对于所有n> = n0。 （也就是你以这样的方式，你的曲线F（N）始终位于或低于该点定义了一个最大值。

大欧米茄使用时，我们有一个渐近下界

和当我们有两者的上限和下限西塔使用。

现在，回到你的question-插入排序有一个O（N²）的复杂性和归并排序为O（n log n）的。在大数值（n 2）往往比（n log n）大。
可以说n = 100。
in insertion sort t他的值将是10000和
合并排序它将是（100日志100）100.2 - > 200。

因此，您可以看到合并排序的运行速度比插入排序快很多。