algorithm - 在渐近分析中添加日志

Question

有一个我正在尝试解决的问题，非常感谢一些帮助！时间复杂度是多少...

for (int j = 1 to n) {
    k = j;
    while (k < n) {
        sum += a[k] * b[k];
        k += log n;
    }
}

外部 for 循环运行 n 次。我不确定如何k+= log n在内部循环中处理。我的想法是它是O（n ^ 2）。将 log(n) 添加到 k 并不能获得额外的 n 个循环，但我认为它小于 O(n*log n) 。显然，这只是一个猜测，任何帮助弄清楚如何在数学上证明这一点将不胜感激！

Answer 1

您可以log(n)在这里将其视为常数。

循环的每次迭代都将执行恒定数量的工作 ( sum+=...; k+=...) 次数等于n/ log(n)。有n循环的迭代。总功是这样n^2 / log(n)。

任何时候你看到一堆这样的操作：

 ---------------------b-------------------------
 |O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
 |O(blah) + O(blah) + O(blah) + O(blah)     .
a|O(blah) + O(blah) + O(blah)               .
 |O(blah) + O(blah)                         .
 |O(blah)     .         .         .         .

它是a*b * O(blah)——想象一下正方形（我放.s 的地方）。它是 2D 矩形（矩形的一半）的常数部分，因此O(a*b).

在上述情况下， b= n、 a=n/log(n)和 O(blah)= O(1)（来自内部循环）

Answer 2

你可以很容易地“总结一下”：

如您所说，外循环具有n步骤。内循环有(k-j) / log n步骤。

那是（大致）：

 n
---
\     (n-j)             n*n
/   -------- = ... = ---------
___  (log n)          2*log(n)
j=1

所以，O((n^2)/log(n))总而言之。

Answer 3

您可以像下面这样正式进行：