java - 求该方法的时间复杂度

Question

我正在尝试计算这段代码的时间复杂度。

我关于这些部分的最后结论是“while”部分的 O(logn)外部 for 循环必须低于 100，所以它的 O(1) 和内部 for 循环是 O(logn) 所以我认为这里的时间复杂度在最坏的情况下是 O(logn) 但我不确定。

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();
    }
}

Answer 1

让我们逐步破解您的代码:

第一个循环，即

 while (i > 100)  
     i = i/3;

运行 O(logm) 次。

for (int k=i ; k>=0; k--) { 
        for (int j=1; j<n; j*=2) {
            System.out.print(k + "\t" + j); 
        } //end inner for loop
        System.out.println(); 
    }

外层循环最多可以运行100次，内层循环即

for (int j=1; j<n; j*=2) {
      System.out.print(k + "\t" + j); 
} //end inner for loop

执行登录次数。

for循环的总时间复杂度=100logn->忽略常量->logn

因此，复杂度为 O(log(m)) + O(log(n))