algorithm - 堆的大哦符号

Question

我试图理解大哦符号。任何帮助，将不胜感激。

假设有一个程序创建一个最大堆，然后推送和删除该项目。

假设有 n 个项目。

要创建一个堆，如果你已经将它读入一个数组，它需要 O(n) 来堆化，然后堆化它。要推送一个项目，它需要 O(1) 并且要删除它，它需要 O(1) 之后要对其进行堆放，每次删除需要 log n 并且对于 n 个项目需要 n log n

所以大的哦符号是 O(n + n log n) 或者，它是 O(n log n) 只是因为我们选择了最大的一个。

Answer 1

在堆中堆积新元素的复杂性是O(logN)，不是O(1)（除非您使用斐波那契堆，但事实并非如此）。

也没有符号O(N + NlogN)比NlogN增长快，N所以这个符号简单地写成O(NlogN)。

编辑：大哦符号仅描述函数的渐近行为，即 - 它增长的速度。当您接近无穷大2*f(x)并且11021392103*f(x)行为相似时，这就是为什么在编写大哦符号时，我们会忽略函数前面的任何常量。

Answer 2

形式上，O(N + N log N)等价于O(N log N)。

也就是说，假设其中每个都隐藏了系数，ala: O( aN + bN log(cN) )。如果您有非常大N的值，则这些系数变得不重要，并且算法仅受其最大项的限制，在本例中为log(N)。

但这并不意味着系数完全不重要。这就是为什么在讨论图算法时你会经常看到作者说“ Floyd-Warshall 算法在 O(N^3) 时间内运行，但系数很小”。

如果我们可以在这种情况下以某种方式写出 O(0.5N^3)，我们会的。但事实证明，系数会根据您实现算法的方式以及运行它的计算机而有所不同。因此，我们满足于渐近比较，不一定是因为它是最好的方法，而是因为没有真正的好选择。

您还会看到诸如“最坏情况：O(N^2)，平均情况：O(N)”之类的内容。这是试图捕捉算法的行为如何随输入而变化。通常，预排序或随机输入可以为您提供平均情况，而邪恶的反派可以构建产生最坏情况的输入。

最后，我要说的是：O(N + N log N)=O(N log N). 这是真的，它是你作业的正确答案。但是我们使用这种 big-O 符号来进行交流，并且随着时间的推移，您可能会发现您觉得它O(N + N log N)更具表现力的情况，也许如果您的算法通常用于 small N. 在这种情况下，不要太担心形式主义——只要清楚你想用它传达什么。