$O((\log n)^{\log \log n})$是否为多项式时间？如何与$O(n^k)$比较？

先直接给结论：是的，它属于多项式时间，而且它的增长速度比任意固定常数$k$对应的$O(n^k)$都要慢。咱们结合多项式时间的定义，用对数变换一步步拆解验证：

先明确多项式时间的定义 #

若算法的运行时间$T(n)$为多项式时间，则存在常数$C、k$，使得当$n$足够大时，$T(n) < Cn^k$。

用对数变换对比增长速度 #

比较两个函数的增长快慢，取对数是个实用技巧——因为对数函数单调递增，对数的大小关系和原函数的大小关系完全一致：

1. 对$(\log n)^{\log \log n}$取自然对数：
   $$\log\left((\log n)^{\log \log n}\right) = (\log \log n)^2$$
2. 对$n^k$取自然对数：
   $$\log(n^k) = k\log n$$

现在只需要证明：不管$k$是多大的固定常数，当$n$足够大时，$(\log \log n)^2 < k\log n$。

咱们换个变量简化理解：令$t = \log n$，当$n$趋向无穷大时，$t$也趋向无穷大，问题转化为证明当$t$足够大时，$(\log t)^2 < kt$。

这一点很容易验证：不管$k$取多大，$t$的线性增长速度远远快于$(\log t)^2$的增长速度。比如当$t$足够大时，$\log t < \sqrt{kt}$，两边平方就能得到$(\log t)^2 < kt$。

把变量换回去，就有$(\log \log n)^2 < k\log n$，两边取指数（指数函数单调递增），最终得到：
$$(\log n)^{\log \log n} < n^k$$

这完全符合多项式时间的定义——存在固定常数$C=1$和任意固定$k$，当$n$足够大时，原函数小于$Cn^k$。

结合示例加深理解 #

你给出的示例里，$2^{\sqrt{\log n}}$取对数是$\sqrt{\log n}$，因为它的增长速度比$k\log n$慢，所以属于多项式时间。而咱们问题中的函数，取对数后是$(\log \log n)^2$，它的增长速度比$\sqrt{\log n}$还要慢（双重对数的平方远慢于对数的平方根），自然也满足多项式时间的要求。

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