算法的复杂性

我正在学习考试，看到了这个问题，所以我做了以下，是不是正确的？

while循环运行在O（log3n）。

for循环运行在大约O（（n-（某些数学））* 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) 。

Answer 2

第一个while循环在O(100*log_3(m)) 。 这应该很容易看到。

对于外部for循环，请注意i最多为100（因为前一个while循环），并且内循环为O(100*log_2(n)) ，因此总渐近极限为O(log_3(m) + log_2(n)) 。