我如何继续计算这个函数的时间复杂度 (f3)？

Question

答案是O(n^6)但我不太确定如何到达那里，尝试使用小数字表明 g 将数字 n 增加到 3 的幂，k=n^3因此k^2=n^6（我认为），但是我如何以数学方式显示它，具体来说，我们是教了一种使用新功能的方法，T(n)但我不确定如何在此处应用它，感谢您的帮助。

int g(int n)
{
    if (n <= 1) return 1;
    return 8 * g(n / 2);
}


void f3(int n)
{
    int k = g(n);
    for (int i = 2; i < k * k; ++i)
        {  printf("*");  }
} 

Answer 1

我们先来分析一下函数g(n)：

g(n) = 8 * g(n/2)

如果您消除递归，这将分解为

g(n) = 8^log_2(n)

并消除对数产生：

g(n) = n^3

现在k*k是n^3*n^3 = n^6，所以循环打印n^6星号。这导致 的时间复杂度O(n^6)。