ε>0时n^{3+ε}*log(n^{3+ε})是否等于O(n^{3+ε})

结论 #

当ε > 0为固定常数时，$n^{3+\epsilon} * log(n^{3+\epsilon}) = O(n^{3+\epsilon})$ 不成立。

推导说明 #

• 首先化简原式中的对数项：根据对数幂运算规则，log(n^{3+ε}) = (3+ε)·log n，其中3+ε是和输入规模n无关的正常数，因此原式可以改写为(3+ε)·n^{3+ε}·log n。
• 回忆大O记号的严格定义：若存在正的常数C和规模阈值n₀，使得对所有n ≥ n₀都满足f(n) ≤ C·g(n)，才有f(n) = O(g(n))。
• 此处取f(n) = (3+ε)·n^{3+ε}·log n，g(n) = n^{3+ε}，代入判定条件可以约掉两边共有的n^{3+ε}项，最终需要验证是否存在常数C使得(3+ε)·log n ≤ C对所有足够大的n成立。显然不成立：当n趋向于无穷大时，log n是单调递增并趋向正无穷的函数，无论选取多大的固定常数C，总能找到足够大的n使得(3+ε)·log n > C，不满足大O的约束条件。

关于你提到的log(ε)的疑问 #

你担心乘以log(ε)会影响复杂度阶数，这里有两个关键点需要澄清：

1. 原式中乘的对数项是和n相关的log(n^{3+ε})，不是和n无关的log(ε)。如果乘的是和输入规模n完全无关的固定常数（比如固定ε取值下的log(ε)，只要ε是预先给定的正常数），这类常数项完全可以被大O记号里的常数C吸收，不会改变复杂度的阶数。
2. 只有当乘的项是随n增长趋向无穷的函数时，才会提升复杂度的阶——比如本题中的log n，虽然它的增长速度比任何形如n^δ（δ>0）的多项式项都慢，但它终归是无界的，无法被常数吸收，因此会让整体的复杂度比n^{3+ε}更高。

补充：该式的正确大O上界应为O(n^{3+ε} log n)，反过来n^{3+ε} = O(n^{3+ε} log n)是成立的。

内容的提问来源于stack exchange，提问作者user18926311