帮助我们发现时间和空间的复杂性

Question

int f2(int n)
{    
    int x, y, z = 0, i;
    for(x = n, i = 0; i < n; i ++, x *= n)
    {
        y = x;
        while (y > 1)
        { 
            y /= 3;
            z += y;
        }
    }
return z;
}

我对第一个循环感到困惑，我的问题是我不知道循环执行了多少次，以及x如何影响一般的代码。

Answer 1

它是:

日志<子> 3 (n) +日志<子> 3 (n <一口> 2> 3 (n <一口> n> 3 (n) n (n + 1)/2

短期内:

n^2log(n)