1 + 2 + 3 + ... + n和算法的示例

Question

什么是复杂性T(n)=1+2+3+...+n？我知道答案是O(n^2).什么是运行时算法的示例T(n)？

编辑:我不是在谈论计算总和1 + 2 + 3 + ... + n,这不是客观的.

Answer 1

什么是具有运行时T(n)的算法示例？

如果你有一个外循环,迭代n次数和内循环,迭代i倍,其中i是外环的指标,内部循环体将被执行T(n)的时间.

这种嵌套循环的一个例子是以下算法:

for i from 1 to n
    for j from 1 to i
        print "$j "
    print "\n"

这是常见作业分配的解决方案,并打印出以下形状的数字金字塔:

1
1 2
1 2 3