两段代码的时间复杂度 [英] Time complexity for two pieces of code

问题描述

我们有两段代码:

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) ?

What is the time complexity of them? I think that the first one is: O(logn), because it's progressing to N with power of 2.
So maybe it's O(log²n) ?

我相信的第二个是:O(nlog2n)，因为它以 2 次跳跃前进，并且还在外循环上运行.

And the second one I believe is: O(nlog2n), because it's progressing with jumps of 2, and also running on the outer loop.

我说得对吗?

推荐答案

我相信，第一个代码将在 O(Log(LogN)) 时间内运行.这样理解很简单

I believe, that first code will run in O(Log(LogN)) time. It's simple to understand in this way

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))

In the second code first piece of code will work in O(LogM) time, because you divide i by 3 every time. The second piece of code C times (C equals 100 in your case) will perform O(LogN) operations, because you multiply j by 2 every time, so it runs in O(CLogN), and you have complexity O(LogM + CLogN)

这篇关于两段代码的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！