主项如何使用大O表示法确定时间复杂度？

Question

我不太理解主要项的概念以及如何使用大O来确定时间复杂度。例如，对于N（100N + 200N^3）+ N^3，它的主要项是什么？如果有人能够解释一下，那将非常有帮助。

- SomeoneAwesome

---

这是表达式的最高幂。以你的例子为例 - N的4次方。 - TDG

我投票关闭此问题，因为它是一个关于算法的一般性问题，而不是根据[帮助]定义的编程问题。关于特定编程问题以外的算法问题可以在计算机科学.SE上提问。 - TylerH

Answer 1

主导项是随着N的增大而变得最大（即占据支配地位）的项。

例如：

 N(100N + 200N^3) + N^3

可以重写为：

 (100 * N^2) + (200 * N^4) + N^3

随着N的增大，N^4将变得更大（与其乘以的200无关）。

因此，这将是O(N^4)。

- Stephen C

---

那么，就时间复杂度而言，它会是什么？O(?) - SomeoneAwesome

@SomeoneAwesome 这将是O(N^4)。 - Kaushal28

@Stephen C，我还有一个问题。如果涉及到“log”，您会怎么做？例如：10MlogM + (N/2) log (N/2) + N/4？ - SomeoneAwesome

@SomeoneAwesome 看到我的 O(g) 定义有误，c 不是 R 的元素，而是 R+ 的元素。 - Aziuth

当涉及到“log”时，你会怎么做？这是数学问题。你可以使用数学来证明（例如）N log N项增长速度比N更快，而N的增长速度比logN更快。（请注意，我们在这里非常不正式。）如果你没有能力自己进行数学证明，请绘制函数图形，或找到一些网页，整理和排序常见的复杂度类别。 - Stephen C

Answer 2

令 f(N) = 100N^2 + 200 N^4 + N^3。随着 N 的增加，f(N) 的值被 200 N^4 项所主导。即使 N^4 项的系数小于低阶项的系数，这种情况也是成立的。

考虑一个更简单的例子，g(N) = N^2 + 4N。当N = 1000时，我们得到g(1000) =10^6 + 4000，这大约是10^6，因为一百万加上（几）千仍然是大约一百万。因此，N^2$项支配了低阶项。即使低阶项的系数很大，在g(N) = N^2 + 10^{100} N中，N^2项也支配了线性项，只是在这种情况下，使二次项超过线性项所需的N值更大。但随着N趋近于无穷大，我们可以通过其主导项来近似一个函数。

关于大O符号，你可以使用其定义证明多项式f(N)可以表示为O(N^k)，其中k是主导项的指数。在你的例子中，我们可以说f(N) = O(N^4)。这种符号会忽略低阶项和主导项系数，因为它们通常在比较不同算法的运行时间时是无关紧要的。

- Ashwin Ganesan

---

所有这些$符号是用来做什么的？ - TDG

@TDG 我以为那些 $ 符号会被转换成方程形式，就像我参加的其他社区（如math.stackexchange.com）一样。那是LaTeX的东西。 - Ashwin Ganesan

我知道了。这里是一个 ` 符号。无论如何，我已经编辑了你的回答。 - TDG

Answer 3

“Dominant” 简单来说就是“长期内增长更快的那一个”。这是我能够最好地表达它的方式。

- Paco G

Answer 4

让我们将你的多项式函数分解成几个部分， F(N) = 100N²+ 200N^4 + N^3 ; g，h，k分别是三个多项式函数 g(N) = 200N^4 , h(N) = N^3 , k(N) = 100N² . h被g所支配，k被h所支配，因此使用传递关系k被g所支配；因此h和k都被g所支配。 我所说的支配在数学上是指当n趋近于无穷大时，分数(h(n)/g(n))或(k(n)/g(n))的极限为零。 因此，要知道哪个函数被支配，您需要研究渐近行为和极限。

这是从this website中举例说明的。

- bwass31