这个函数会是 O(n^2log_2(n)) 吗？

Question

所以我得到了一个像 65536 n² + 128 n log₂n

这样的函数

而这将是 O(n² log₂n) 的唯一方法是 if

C = 65664，n0 = 2 对于所有 n ≥ 2 因为

C1 = 65536 n1 = 2 当 65536 ≤ C1*n² 和
当 128 ≤ C2*n

时，C2 = 128 n2 = 1

但是我为常数选择的数字似乎有点高，有没有办法检查这个？

Answer 1

O(65536 n² + 128 n log₂n) 与 O(n² + n log₂n) 因为您可以忽略乘法常数。 O(n² + n log₂n) 等于 O(n²) 因为 n² 比 n 增长得更快 log₂n.

此外，顺便说一下，在 Big-O 分析中，对数的底数并不重要。所有对数都以相同的速率增长。毕竟log₂n = log n / log 2，乘法常数是可以分解出来的。你可以简单地说 log n 而不是 log₂n.

警告： 从技术上讲，65536 n² + 128 n log _{实际上是一个正确的陈述2}n ∈ O(n² log₂n) 因为 Big-O 给出 an 上限，但不是严一。 O(n²) 是一个 下限 上限，如果这有意义的话。

也就是说，你不应该想出 O(n² log₂n)。那只是不小心把加法变成了乘法的结果。根据经验，如果你在一个 Big-O 公式中将多个东西加在一起，你只需要找出其中一个增长最快，然后丢弃其他的。

Answer 2

让我们在这里简化方程式，因为常数并不重要：

n² + n log₂n

因为 n² > n log₂n 随着 n 接近无穷大

Big-O 是 O(n²) 因为 n² 是上限。