我有点困惑。如果一个算法的时间复杂度给出为
那么在大 O 符号表示法中是仅为 还是要保留对数符号?
O(n^2)
和 O((n^2)*log(n))
是有区别的。这里需要一个正式的数学证明。
我们定义以下变量和函数:
N
- 算法输入长度,
f(N) = N^2*ln(N)
- 计算算法执行时间的函数。
让我们确定这个函数的增长是否渐进地受到 O(N^2)
的限制。
根据渐进符号 [1] 的定义,如果对于所有足够大的值 x
,f(x)
的绝对值最多是 g(x)
的正常数倍,则 g(x)
是 f(x)
的渐进界。也就是说,当且仅当存在一个正实数 M
和一个实数 x0
,使得
|f(x)| <= M*g(x) 对于所有 x >= x0 (1)
M
和一个实数N0
,使得:
|N^2*ln(N)| <= M*N^2 for all N >= N0 (2)
显然,这样的M
和x0
不存在,因为对于任意大的M
都有N0
,使得
ln(N) > M for all N >= N0 (3)
因此,我们已经证明了N^2*ln(N)
不是由O(N^2)
渐近界定的。您需要记录日志,因为log(n)会随着n的增加而增加,并在乘法运算时增加整体复杂度。
通常情况下,只有当一个常数可以移除时才可以删除它。例如,如果您有O(2 * n^2),则只需说复杂度为O(n^2),因为在一台性能提升两倍的计算机上运行不应影响复杂度。
同样地,如果您的复杂度是O(n^2 + n^2),则可以得到上述情况,只需说它是O(n^2)。由于O(log(n))比O(n^2)更优,如果您有O(n^2 + log(n)), 您应该说复杂度为O(n^2),因为它甚至比O(2 * n^2)还要小。
O(n^2 * log(n))不符合上述情况,因此您不应将其简化。
O(n2 + n)
可以写成 O(n2)
,因为当我们增加 n
时,n2 + n
和 n2
之间的差异变得不存在。因此可以写成 O(n2)
。O(n2logn)
中,随着 n
的增加,n2
和 n2logn
之间的差异会增加,不像上面的情况。
因此,logn
保持不变。