計算嵌套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

回答