java - 算法的复杂性(嵌套循环)

Question

我得到了这样一个算法的代码:

1  sum =0;
2    for(i=0; i<n; i++)
3      for(j=1; j<= n; j*=3)
4        sum++;

有人告诉我这个算法在 O(nlogn) 中运行，其中 log 以 3 为底。所以我得到第二行运行 n 次，并且由于第 3 行独立于第 2 行我必须将两者相乘才能得到大 O，但是，我不确定答案如何是 nlogn(以 3 为基数登录)，他们是否保证每次都能解决这个问题？似乎对于嵌套循环，每次都会发生不同的情况。

Answer 1

你被告知的是正确的。该算法运行于 O(nlog(n)) .第三行:for(j=1; j<= n; j*=3)在 O(log3(n)) 中运行因为你每次乘以 3。为了更清楚地看到它解决问题:你需要将 1 乘以 3 多少次才能得到 n。或者 3^x = n .解决方案is x = log3(n)