algorithm - 算法复杂度的推导

Question

刷新算法复杂性，我在看这个例子：

int x = 0;
     for ( int j = 1; j <= n; j++ )
        for ( int k = 1; k < 3*j; k++ )
             x = x + j;

我知道这个循环最终是 O(n^2)。我相信内循环执行 3*n 次（ 3(1+2+...n) ），外循环执行 n 次。所以，O(3n*n) = O(3n^2) = O(n^2)。

但是，我正在查看的源将内部循环的执行扩展到：3(1+2+3+...+n) = 3n^2/2 + 3n/2. 谁能解释3n^2/2 + 3n/2执行时间？

Answer 1

对于每个 J 你必须执行 J * 3 次内部循环迭代，所以你的命令x=x+j最终将被执行 n * 3 * (1 + 2 + 3 ... + n) 次，算术级数的总和是 n*(n+ 1)/2，所以你的命令将被执行：

3 * n * (n+1)/2 which is equals to (3*n^2)/2 + (3*n)/2

但是大 O 并不是迭代的多少，它是关于渐近测量，所以在表达式 3*n*(n+1)/2 中需要删除 consts（将它们全部设置为 0 或 1），所以我们有 1* n*(n+0)/1 = n^2

关于这种情况下大 O 计算的小更新：从 3n(n+1)/2 中生成大 O，对于大 O，您可以想象 N 是无穷大，所以：

infinity + 1 = infinity
3*infinity = infinity
infinity/2 = infinity
infinity*infinity = infinity^2

所以你在这之后你有N^2

Answer 2

可以使用 Sigma 表示法找到算法的精确精度，如下所示：

已经过经验验证。

Answer 3

Big O表示法给出了算法的渐近运行时间的上限。它不考虑低阶项或常数因子。因此 O(10n ² ) 和 O(1000n ² + 4n + 56) 仍然是 O(n ² )。

您正在做的是尝试计算算法中操作的数量。但是Big O没有说明确切的操作次数。它只是为您提供了在不利输入时可能发生的最坏情况运行时间的上限。

Answer 4

从 1 到 m 的整数之和为 m*(m+1)/2。在给定的问题中，j 从 1 变为 n，k 从 1 变为 3*j。因此，k 上的内部循环执行 3*(1+2+3+4+5+...+n) 次，该系列中的每一项代表 j 的一个值。这给出了 3n(n+1)/2。如果你扩展它，你会得到 3n^2/2+3n/2。不过，整个事情仍然是 O(n^2)。您不在乎您的执行时间是否以二次方和线性方式增加，因为线性被二次方淹没了。