算法时间复杂度分析求助：如何化简log₂(n)*log₄(n⁴)的大O表示？

int f(int n) {
    int j = n;
    while (j > 1) {
        int i = 1;
        while (i <= n * n * n * n) {
            i = 4 * i;
            print("*");
        }
        if (j / 2 > 1) {
            print(" ");
        }
        j = j / 2;
    }
    return j;
}

你的初步分析方向是对的，外层循环次数为$\log_2(n)$，内层循环次数为$\log_4(n^4)$，接下来一步步化简：

• 化简内层循环的$\log_4(n^4)$
  根据对数幂法则：$\log_b(a^k) = k \cdot \log_b(a)$，可得$\log_4(n^4) = 4 \cdot \log_4(n)$。
  再用对数换底公式：$\log_b(a) = \frac{\log_c(a)}{\log_c(b)}$，将底数转为2，$\log_4(n) = \frac{\log_2(n)}{\log_2(4)} = \frac{\log_2(n)}{2}$。
  代入后计算：$4 \cdot \frac{\log_2(n)}{2} = 2\log_2(n)$，大O表示中常数因子可忽略，因此内层循环时间复杂度为$O(\log_2(n))$，也可写成通用的$O(\log n)$（对数底数在大O中属于常数因子，不影响量级）。

• 合并内外层复杂度
  外层循环次数为$O(\log_2(n))$，内层每次执行的复杂度为$O(\log_2(n))$，因此总时间复杂度为$O(\log_2(n) \cdot \log_2(n)) = O((\log_2 n)^{2)$，也就是通用写法$O(\log}2 n)$。

你提到的$\log_2(n) \cdot \log_4(n)$等价于$\log_2(n) \cdot \frac{\log_2(n)}{2} = \frac{(\log_2 n)^{2}{2}$，同样属于$O(\log}2 n)$量级；而$\log_2^2(n)$就是$(\log_2 n)^2$，和化简结果是同一量级。

最终的大O表示形式为**$O(\log^2 n)$**（或$O((\log n)^2)$）。

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