算法的复杂性（嵌套循环）

Question

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

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

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

Answer 1

在第二个循环中你有 j *= 3，这意味着你可以将 n 除以 3 log3(n) 次。这给了你 O(logn) 复杂性。
因为你的第一个循环有一个 O(n) 你最后有 O(nlogn)

Answer 2

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

Answer 3

是的。算法运行 nlog(n) 次，其中 log 以 3 为底。

计算复杂度的最简单方法是计算完成的操作数。

外层for循环运行n次。让我们计算每个内部 for 循环对每个 n 运行多少次。所以对于 n=1,2，内部 for 循环运行 1 次。对于 n=3,4,5,6,7,8 内部 for 循环运行 2 次。等等...

这意味着对于每个 n，内部 for 循环以对数时间 (log(n)) 运行。

因此 n*log(n) 将是总复杂度。