对数函数的渐近复杂度

Question

我知道在复杂度方面，O(logn)比O(n)快，O(n)比O(nlogn)快，O(nlogn)比O(n2)快。 但是O(n2)和O(n2log)，或者O(n2.001)和O(n2log)呢：

T1(n)=n^2 + n^2logn

这个函数的时间复杂度分别是大O、omega和小o？小o又是什么意思？

T2(n)=n^2.001 + n^2logn

现在的大O符号有什么区别吗？ 我不太明白如何比较logn和n的幂。例如，logn大约等于n^0.000000...1还是n^1.000000...1？

- Joseph D

---

我认为你忽略的关键点是：log(n)增长速度比任何正幂次的n都要慢，无论这个幂次有多小。因此，log(n)并不近似于n的任何幂次。 - Michael J. Barber

你可以说的一件事是：log(n) = n^{o(1)}。也就是说，它在任何epsilon > 0的情况下都渐近小于n^{epsilon}。 - Chris Beck

Answer 1

O(n^k)比O(n^k')更快，其中k，k' >= 0且k' > k

O(n^2)比O(n^2*logn)更快

请注意，您只能忽略常数，不能忽略涉及输入大小的任何内容。

因此，T(n)=n^2 + n^2logn的复杂度将是两者中较差的一个，即O(n^2logn)。

---

小o符号

松散地说，小o符号是一个保证的上限。是的，它被称为小o，而且它更加严格。

n^2 = O(n^k)对于k >= 2，但n^2 = o(n^k)对于k > 2

实际上，大O符号占据了大部分舞台。

---

那么T(n)= n^2.001 + n^2logn呢？

我们有n^2.001 = n²*n^0.001和n² * log(n)。

为了解决这个问题，我们需要弄清楚n^0.001或log(n)会在足够大的n下成为更大的函数。

事实证明，形式为n^k的函数，其中k > 0，将最终取代log(n)，对于足够大的n。

同样是这种情况，在这种情况下T(n) = O(n^2.001)。

但实际上，log(n)将大于n^0.001。

(10³³⁰⁰)^0.001 < log(10³³⁰⁰) (1995.6 < 3300)，而在这种情况下的足够大的n将只有约10³⁶⁵⁰，这是一个天文数字。

再次提到，10³⁶⁵⁰。宇宙中有10⁸²个原子。

- axiom

---

但是对于 T(n)= n^2.001 + n^2logn 呢？ - Joseph D

你的图表有误导性。任何n的幂都能支配log(n)。由于n^0.001是一个增长非常缓慢的函数，因此在这些线相交之前，需要一个巨大的n值。 - Michael J. Barber

@axiom 我从每个式子中消除了n^2的公共因子。 - Michael J. Barber

顺便说一下，我尝试在对数坐标轴上绘制曲线，但当我达到图形程序能处理的最大浮点数限制时，它们仍然没有相交。因此，任何可以表示为双精度的数字仍处于“足够小以至于常数因子有影响”的范围内；这包括诸如可能的国际象棋棋盘配置数量或可观察宇宙中的原子数量等微不足道的小数字。 - Michael J. Barber

让我们在聊天中继续这个讨论。 - axiom

Answer 2

T(n)=n^2 + n^2logn

这个函数的大O和omega是什么？另外，什么是小o？

引用之前的答案:

不要忘记，大O符号代表一个集合。 O(g(n)) 是所有函数 f 的集合， 这些函数不会增长得比 g 快，形式上说，意味着存在 C 和 n0， 使得对于每个 n >= n0，我们有 |f(n)| <= C|g(n)|。 表达式 f(n) = O(g(n)) 是一种简写，表示 f(n) 在集合 O(g(n)) 中。

此外，您可以将大O视为≤，将小o视为<（reference）。因此，您更关心找到相关的大O界限而不是小o。在您的情况下，使用大theta符号=甚至更合适。由于n^2 log n支配了n^2，所以以下命题成立：

T1(n)=n^2 + n^2logn = Ө(n^2 logn)

现在是第二部分。log n增长非常缓慢，甚至n^e, e > 0也可以支配它。有趣的是，你甚至可以证明，当n趋向于无穷大时，lim n^e/(logn)^k=inf。从这里可以得出，n^0.001支配了log n。

T2(n)=n^2.001 + n^2logn = Ө(n^2.001).

如果 f(n) = Ө(g(n))，那么也成立 f(n) = O(g(n))，因此回答你的问题：

• T1(n)=O(n^2 logn)
• T2(n)=O(n^2.001)

- sve