关于时间复杂度O(log²(n))与O(n)的比较及相关疑问

嘿，这个问题问到点子上了！先给你拍板定论：不管你给$\log(n)$套多少有限次方——哪怕是100次方、1000次方——它的增长速度永远追不上线性的$O(n)$，不存在所谓的“临界点”让前者超过后者。

为啥这么说呢？咱们从直观和数学两个角度唠唠：

• 直观感受：$\log(n)$本身增长就慢得离谱，比如以2为底的话，n到$10^{6$时$\log_2(n)$才约20，平方后也才400，和n的100万比差了好几个数量级；就算n膨胀到$10}{100}$，$\log_2(n)$也就300多，平方后是十几万，可n是1后面跟100个0，完全不是一个量级。就算你把$\log(n)$升到10次方，结果还是远小于n。
• 数学证明：从极限的角度看，对任意有限的正数k，$\lim_{n \to \infty} \frac{(\log n)^k}{n} = 0$。这个式子的意思就是，当n趋向无穷大时，$(\log n)^k$相对于n来说会趋近于0，换句话说，n的增长速度是碾压式的，不管k取多大的有限值，都改变不了这个结果。

另外你一开始提到的$O(\log^2(n))$就是$O((\log n)^2)$，不是$O(\log(\log n))$，这点你理解得完全正确，行业里很多时候会用这种简写来避免括号嵌套的繁琐。

备注：内容来源于stack exchange，提问作者Henry Deutsch