java - 算法的复杂性

Question

我正在备考，看到这道题，所以我做了下面的，对吗？

while 循环的运行时间为 O(log3n)。

for 循环的运行时间约为 O((n-(some math))*log2n) 所以因为我有一个线性的减号，所以我说整个方法的运行时间为 O(nlogn)，除非我错了，有点像

O((n-(n/log3n))*log2n) <- 不完全是，但不是很清楚。

这里的负值是不是线性的？如果不是什么是正确的 bigO？

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 循环在 O(logm) 中运行。

while 循环结束后，i <= 100，所以下一个 for 循环最多运行 100 次。

对于外循环的每次迭代，内循环将运行 O(logn) 次。所以总时间是 O(logm + 100*logn) = O(logm + logn)。