我得到了这样一个算法的代码:
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 为基数登录)，他们是否保证每次都能解决这个问题？似乎对于嵌套循环，每次都会发生不同的情况。
最佳答案
你被告知的是正确的。该算法运行于 O(nlog(n)) .第三行:for(j=1; j<= n; j*=3)在 O(log3(n)) 中运行因为你每次乘以 3。为了更清楚地看到它解决问题:你需要将 1 乘以 3 多少次才能得到 n。或者 3^x = n .解决方案is x = log3(n)
关于java - 算法的复杂性(嵌套循环)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34113485/