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) 次，总和 Arithmetic progression是 n*(n+1)/2，所以你的命令将被执行:

3 * n * (n+1)/2 等于 (3*n^2)/2 + (3*n)/2

但是大O不是迭代多少次，而是关于渐近测度，所以在表达式3*n*(n+1)/2中需要去掉常量(将它们全部设置为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