算法复杂度的推导

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，可以想象比N更大的O是无穷大的，因此：

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

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

Answer 2

从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+3n/2，但整件事情仍然是O(n^2)。你不在乎你的执行时间是否呈二次和线性上升，因为线性被二次二次曲线淹没。

Answer 3

使用这样的Sigma表示法可以找到算法的精确性：

​

​

这是经验之谈。