问询：2^((logn)^2)与n³的增长阶比较及拟多项式时间判定

一、2^((logn)2)是否属于拟多项式时间？ #

拟多项式时间的核心定义是：算法时间复杂度可表示为 **n^{O(logn)**（等价形式为2}(O((logn)^2))），其中n为输入的二进制规模。

通过指数与对数的转换，可将2^((logn)2)改写为n^logn：
已知n = 2^(log₂n)，因此n^logn = (2^(log₂n))^logn = 2^((log₂n)·logn) = 2^((logn)^2)（对数底数不影响增长阶，仅差常数因子）。

显然n^logn属于nO(logn)的范畴（取O(logn)中的常数为1即可），因此2^((logn)2)属于拟多项式时间复杂度。

二、比较2^((logn)2)与n³的增长阶 #

比较两个函数的增长阶，可通过取对数将复杂函数转换为易比较的形式：

1. 对2^((logn)2)取以2为底的对数：
   log₂(2^((log₂n)^2)) = (log₂n)^2

2. 对n³取以2为底的对数：
   log₂(n³) = 3log₂n

对比转换后的两个函数：
当n足够大时（如n > 2³=8），log₂n会大于3，此时(log₂n)^2 = log₂n × log₂n > 3log₂n，且随着n持续增大，(log₂n)^2的增长速度会远快于3log₂n。

由于对数函数是单调递增的，原函数的增长阶关系与对数后的结果一致：2^((logn)2)的增长速度远快于n³。

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