两段代码的时间复杂度

Question

我们有两段代码:

int a = 3; 
while (a <= n) {
    a = a * a;
}

和:

public void foo(int n, int m) { 
    int i = m; 
    while (i > 100) 
        i = i / 3; 
    for (int k = i ; k >= 0; k--) { 
        for (int j = 1; j < n; j*=2) 
            System.out.print(k + "\t" + j); 
        System.out.println(); 
    } 
}

它们的时间复杂度是多少？我认为第一个是:O(logn),因为它以2的幂进展到N
所以也许它是O(log ² n)？

我认为第二个是:O(nlog2n),因为它正在以2的跳跃进行,并且还在外循环上运行.

我对吗？

Answer 1

我相信,第一个代码将在O(Log(LogN))时间内运行.用这种方式理解起来很简单

1. 在第一次迭代之前,你有3个幂1
2. 在第一次迭代后,你有3个幂2
3. 在第二次迭代后,你有3个幂4
4. 在第三次迭代后,你有3个幂8
5. 在第四次迭代后,你有3个幂16,依此类推.

在第二个代码中,第一段代码将在O(LogM)时间内工作,因为每次将i除以3.第二段代码C次(在你的情况下C等于100)将执行O(LogN)操作,因为你每次将j乘以2,所以它在O(CLogN)中运行,并且你有复杂度O(LogM + CLogN) )