1

有人可以帮我理解如何找到以下循环的时间复杂度：

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

我在这里找到了解决方案，即 n 2 / log(n)。

很明显，外循环需要 n 次，但对于内循环，我被卡住了。n / log n 因子从何而来？

我试图逐个学期地遵循它，但无法继续

1st time k = 1,
2nd time k = 1 + log n
3rd time k = 1 + log n + log n  //   (2 log n)

stuck here :(

我怎样才能找到一种模式，或者我应该遵循哪些最佳步骤来获得此类代码的时间复杂度？

4

2 回答 2

1

试着这样想：外循环肯定会运行 O(n) 次，所以如果你能确定内循环完成的工作量，你可以将它乘以 O(n) 以获得总数的上限完成工作。

那么让我们看一下内部循环。请注意，当循环迭代时，k 将采用值 j、j + log n、j + 2 log n、...、j + i log n，其中i是循环运行的迭代次数。

所以考虑一下循环可以执行的最大次数。它在 k ≥ n 时立即停止，这意味着它在 j + i log n ≥ n 时立即停止，因此在 (n - j) / log n 次迭代之后，循环将停止运行。如果我们想为这种情况发生的次数获得一个保守的上限，请注意在最坏的情况下我们有 j = 1。这意味着这个循环的最大迭代次数是 (n - 1) / log n = O(n / log n)，所以内循环的每次迭代都会做 O(n / log n) 的工作。

将每个循环迭代的 O(n / log n) 工作乘以 O(n) 次迭代会产生 O(n 2 / log n) 的总体结果，这是期望的结果。

希望这可以帮助！

于 2013-09-06T20:17:48.840 回答
1

显然，外循环按 n 顺序运行。所以问题是：内循环需要多长时间？循环在 时终止k >= n，k从 开始j并以 为步长递增log(n)。大约需要

n / log(n)

1从到n的迭代次数log(n)（给出或取舍入误差）。但我们并不总是一路从1to n——有时我们从10to n, or 20, or n/2...

(n - i) / log(n)

当我们从而i不是1（或0...）开始时，我们可以将内部循环显式执行的总次数写为总和：

total number = sum(i = 1 to n, (n - i) / log(n))
             = sum(i = 1 to n, n / log(n)) - sum( i = 1 to n, i / log(n))

             = O(n * n / log(n)) - something smaller than that.

“较小的术语”大约是第一个术语的一半，因为

sum( i = 1 to n, i ) = n * (n + 1) / 2;

但是当我们查看计算的顺序时，这样的常数并不重要——我们只想知道n变大时会发生什么，所以虽然你可能想说算法在 中运行，但我们只是说它运行在O( (1 - 0.5) * n2/log(n))O( n2/log(n))

你现在能看到吗？

于 2013-09-06T20:18:24.173 回答