查找运行三个循环的代码的时间复杂度。

Question

我有这段代码，我想找出它的时间复杂性。我正在为面试做准备，我认为这次面试有点困难。

int foo (int n) 
{
    int sum = 0;
    int k, i, j;
    int t = 2;

    for (i=n/2; i>0; i/=2)
    {
        for(j=0; j<i; j++) 
        { 
            for(k=0; k<log2(t-1); k++) 
            {
                sum += bar(sum);
                // bar time-complexity for all inputs is O(1)
            }
        }
        t = pow(2, i);
    }
}

我不知道为什么，但我无法绑定这个表达式，并发现一个复杂的。

对如何解决这个问题有什么帮助吗？

Answer 1

让我们把它写下来如下：

(n/2)*log(1) + (n/4)*log(3) + ... + 1*(log(n-1)). Which is equal to:

​

​

< n * [log(2^i)/(2^i) for i in range 1...n] .
= n * [log(2)/2 + log(4)/4 + log(8)/8 + ... + log(n)/n)] 

这是给O(n)的

Answer 2

既然你没有表现出任何进步，我就给你一个最高级的提示：

• 设log_t = log2(t).log_t作为i的函数是什么？
• 注意，外部循环被执行log2(n)次。
• 执行j循环的总次数是多少？
• 选择n的示例值，例如32。对于i的每个值，执行sum +=语句多少次？你能基于n推广这方面的方程式吗？