嵌套循環時間分析

好吧，我考慮的算法類和我遺憾的是學習的考試... ..我無法理解嵌套循環時間分析背後的概念嵌套循環時間分析

有這三個環路代碼

for (i=1->n) 
for (j=1->i) 
    for (k=1->i) 
    x=x+1;

我不知道如何找出答案：■ 任何回答將是一個很大的幫助感謝鄉親:)

來源

2013-03-02 geekybedouin

當i=1，K-循環運行1次和j循環運行1次。總計= 1.1 = 1次
當i=2時，k循環運行2次，j循環運行2次。總數= 2.2 = 4次
當i=3時，k循環運行3次，j循環運行3次。總數= 3.3 = 9次
當i=n時，k循環運行n次，j循環運行n次。算法的時間複雜度爲O（1 + 2^2 + 3^2 + ... n^2）= O（n（n + 1）（2n + 2） 1）/ 6）= O（N^3）

來源

2013-03-02 16:21:12 jitendra

另一個問題請：爲（I = 1 - > N）爲 - 爲（K = 1 - > J）（J = 1> I） //代碼在這裏 – geekybedouin 2013-03-02 16:26:37

@Umar現在找出如何做到這一點，就像我做到的一樣。我詳細寫了答案，以便學習更容易。 – jitendra 2013-03-02 16:29:22

好的..你能否只檢查一下我的答案嗎？當i = 1時，j循環運行1次，k運行1次所以它的1.1 = 1 當i = 2時，j循環運行2次，k運行3次，所以當i = 3時，k = 3運行3次，j運行3次，k運行6次，所以3.6 = 18 – geekybedouin 2013-03-02 16:35:16

您需要總結的循環，這是需要被計算出的只是多個西格瑪：

Sigma Calculation

在該內部西格瑪是你在最內層循環內所做的複雜性。

來源

2013-03-02 16:29:34

甜蜜的方程式，但你有第二個錯誤的總和。這只是我^ 2，而不是我（i + 2）/ 2。 – 2013-03-02 16:47:05

Yeap ..將修復 – 2013-03-02 16:49:24

嵌套循環時間分析

回答

相關問題