計算時間複雜度

我在計算內部循環中的時間複雜度方面受到了重視。計算時間複雜度

讓我們考慮以下情況。

案例1：

for(int i = 0; i <= n; i++) - O(n) 
{ 
    for(int j = 0; j <= i; j++) - O(?); 
    { 
      //Some thing goes here 
    } 
}

這裏內環得到執行到珍惜i每次。

所以，我可以告訴喜歡，在爲內環複雜一些O(i)，

和總體複雜性是O(N) * O(I); ie: O(N*I)

可能在一些簡單的方式有人解釋，這樣我就可以看得懂計算。

謝謝。

來源

2016-04-04 NANDAKUMAR

的總時間複雜度爲Ø（ñ²）（事實上，它甚至Θ（ñ²））。

內環具有複雜性O（i）。然而，n與我，所以只是說整個事情有複雜性O（ni）是錯誤的。內循環體將運行0 + 1 + 2 +⋯+ Ñ =（ñ² + Ñ）/ 2 =Θ（ñ²）倍。

來源

2016-04-04 15:26:55

嗨，你可以分享更多。我對這種執行時間複雜性是新的.. ，並且還可以分享更多關於方程式，（n 2 + n）/ 2 =Θ（n 2）次的內容。謝謝。 – NANDAKUMAR

@ user3663241：評論不是我給出漸近表示法的全面介紹的最佳位置。然而，[麻省理工學院6.042課程筆記]第15.5節（http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2010 /readings/MIT6_042JS10_chap15.pdf）是一個很好的描述。 –

在我結束之前，你會問我要解釋一個簡單的例子。
我們caliculate基礎上，最內層的循環執行多少次
考慮這種情況下的時間複雜度：

for(i=0;i<n;i++){ 
    for(j=0;j<n;j++){ 
    .... 
    } 
}

這裏的外循環執行n次，在每次迭代的內部循環爲n執行倍。
第一次迭代 - N的
2ST迭代 - N的
3ST迭代 - N的
。
。
。
第n次迭代-n
所以內循環執行n * n次，所以它是O（n^2）。
現在我們caliculate你問什麼

for(int i=0;i<=n;i++){ 
    for(int j=0;j<=i;j++){ 
     //Some thing goes here 
    } 
}

在這裏，外環爲n次執行的情況。並且在每次迭代中，內循環都會執行i次。
1st迭代-1
第2次迭代-2
第3次迭代-3
。
。
。
第n次迭代-n
所以當我們caliculate這將是
1 + 2 + 3 + ... + N = N（N + 1）/ 2
這基本上是爲O（n^2）。 :)

來源

2016-04-04 15:41:04 fsdfds

嗨，謝謝。得到了解釋。但只有一個問題。 n * [n（n + 1）/ 2]是最終結果。做完數學後，我可以得到（n^3 + n^2）/ 2 ......我可以知道，如何到達最後的答案O（n^2）....可以嗎？請澄清這一個... 在此先感謝... – NANDAKUMAR

它不是n * [n（n + 1）/ 2]。它只是n（n + 1）/ 2。如果它是（n^3 + n^2）/ 2，它將是O（n^3）。 – fsdfds

嗨，但是這個O（N）屬於外部循環的權利，你沒有包括在數學中。我的意思是外部循環*內部循環，所以它就像n * [n（n + 1）]/2向右...... [這裏O（n）是外部循環，n（n + 1）/ 2是for內部循環。]請糾正我，如果我錯了，請給我路線，瞭解更多。提前致謝。 – NANDAKUMAR

計算時間複雜度

回答

相關問題