關於各種嵌套for循環算法的時間複雜度

Question

我是否對此問題SO柱：Understanding How Many Times Nested Loops Will Run

在有3嵌套for循環的一般公式爲：N（N + 1）（N + 2）/ 3 。我真的不知道爲什麼第二個內部循環運行n + 1次，而外部循環運行n次（在內部循環退出for循環之前不會再運行一次嗎？無論哪種方式......通用公式是

n(n+1)(n+2)...(n+r-1) 
--------------------- 
     r! 

r是嵌套循環的數量。

我還是想知道，這個公式永遠是嵌套循環相同的，如果根據比較結果是什麼裏面的for循環它的變化。 ..如果它是基於比較，那麼如果在考試中我給出了一些不同的循環，我該如何確定公式？如果for循環的比較不同於該循環，我該如何生成或提出此公式？在創建該公式的SO帖子中進行比較？

Answer 1

你必須訓練自己的思想認識並遵循執行模式，並針對具體情況提出一個公式。一般的經驗法則是，如果一個for循環將運行它內部的代碼x次，並且它內部有一個運行y次的循環，那麼內部循環內的代碼將運行x*y次。

for循環的最常見的類型1在零和增量開始，直到它達到一定的數量，就像這樣：

for(int i = 0; i < x; i++) 
    for(int j = 0; j < y; j++) 
     for(int k = 0; k < z; k++) 
      // code here runs x * y * z times 

要回答你的問題，如果你改變任何for的任何部分循環，它會改變執行內部代碼的次數。您需要通過考慮邏輯代碼執行來確定執行次數。

for(int i = 1; i < x; i++) 
    for(int j = 0; j < y * 2; j++) 
     for(int k = 0; k < z; k += 2) 
      // code here runs (x - 1) * (y * 2) * (z/2) times 

在上面的示例中，每個for循環都以不同的方式調整。請注意運行次數的總體公式如何保持相同，但現在每次循環每次運行時運行的次數都不相同。

當循環的變量影響多個循環時，事情變得更加複雜。

for(int i = 0; i < x; i++) 
    for(int j = i; j < y; j++) // notice how `j` starts as `i` 
     // Code here runs `y` times the first time through the outer loop, 
     // then `y - 1` times, 
     // then `y - 2` times, 
     // ... 
     // if x < y, the pattern continues until the xth time, 
     // when this loop runs `y - x` times. 
     // if x > y, the pattern will stop when y == x, and 
     // code here will run 0 times for the remainder of 
     // the loops. 

所以在最後一個例子，假設x < y，循環運行y + (y-1) + (y-2) ... + (y-x)倍。

Answer 2

它根據內部值進行更改。 示例。

 for (int i = 0; i < 100; i++) 
     { 
      //this loop will run 100 times. 
      for (int i1 = 0; i1 < 100; i++) 
      { 
       // This will run 100 times every outer loop int. 
       // This means that for each index i in the outer loop this will run 100 times. 
       // The outer loop runs 100 time and this runs 10,000 times in total. 
      } 
     } 



     for (int i = 0; i < 100; i++) 
     { 
      //this loop will run 100 times. 
      for (int i1 = 0; i1 < 10; i++) 
      { 
       // This will run 10 times every outer loop int. 
       // This means that for each index i in the outer loop this will run 10 times. 
       // The outer loop runs 100 time and this runs 1,000 times in total. 
      } 
     } 

一個更簡單的方法來看待它可能是這樣的。

 for (int i = 0; i < 10; i++) 
     { 
      //this loop will run 10 times. 
      Console.WriteLine("int i = " + i.ToString()"); 
      for (int i1 = 0; i1 < 10; i++) 
      { 
       // This will run 10 times every outer loop int. 
       // This means that for each index i in the outer loop this will run 10 times. 
       // The outer loop runs 10 time and this runs 100 times. 
       Console.WriteLine("int i2 = " + i2.ToString()"); 
      } 
     } 

這會輸出這個。

 int i = 0 
     int i2 = 0 
     int i2 = 1 
     int i2 = 2 
     int i2 = 3 
     int i2 = 4 
     int i2 = 5 
     int i2 = 6 
     int i2 = 7 
     int i2 = 8 
     int i2 = 9 
     int i = 1 
     int i2 = 0 
     int i2 = 1 
     int i2 = 2 
     int i2 = 3 
     int i2 = 4 
     int i2 = 5 
     int i2 = 6 
     int i2 = 7 
     int i2 = 8 
     int i2 = 9 

等等。

該公式基於內部循環數。 （當循環結束時開啓。）