计算嵌套for循环的代价

我想根据n的函数来计算以下算法的成本。计算嵌套for循环的代价

for i:= 1 to n do 
    for j:= i to n do 
    k:=0

据我所知，内部的for循环将迭代（N-1）+（N-2）+ ...（NN）次，但我不知道如何在数学表达这个更简单的形式。我怎样才能做到这一点？

2016-01-13 ar2223

(n-1) + (n-2) + .... (n-n)等于从0到N-1的所有整数之和。因此，它是等于第N-1 triangular number，其可以与式

Tn = n * (n+1)/2

即相当于（1/2）中找到* N^2 +（1/2）* N。

在计算Big O复杂性时，您会丢弃常数乘法器和除快速增长的组件外的所有组件，因此需要执行(1/2)*n^2 + (1/2)*n步骤的算法在O（n^2）时间内运行。

2016-01-13 14:23:55 Kevin

内部循环平均迭代次数为（≈＆frac12; n）次。在“大O”表示法中，您只关心最大的因素。也就是说，例如，如果您有：

ñ³ + N +的log（n）+ 1234

那么唯一重要的事情是n ³因素，因此为O（n ³）。

所以你的情况：

＆frac12; N×n个=＆frac12; N ²

这是O（n ²），因为＆frac12;没关系。

2016-01-13 14:26:10

回答