java - 两段代码的时间复杂度

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 )