2013-04-24 48 views
1

嘿我試圖找出嵌套循環的增長率,我知道第一個循環將會運行100次,因爲它只能運行100次,但第二循環我不太確定。 任何人都可以幫助我?這些循環可以執行多少次?

29 for (int i = 0; i < MAX; ++i) 
30 { 
31  for (int j = 0; m[i] < m[j] && m[j] != 0; ++j) 
32  { 
33  product = product + (m[i] * n[j]); 
34  } 
35 } 

完整的代碼是在這裏

01 const int MAX = 100; 
02 int lowerCount; 
03 int higherCount; 
04 int equalCount; 
05 int product; 
06 
07 lowerCount = higherCount = equalCount = 0; 
08 product = 0; 
09 
10 for (int i = 0; i < MAX; i++) 
11 { 
12  if (m[i] < n[i]) 
13  { 
14   ++higherCount; 
15  } 
16  else 
17  { 
18  if (m[i] == n[i]) 
19  { 
20   ++lowerCount; 
21  } 
22  else 
23  { 
24   ++equalCount; 
25  } 
26  } 
27 } 
28 
29 for (int i = 0; i < MAX; i++) 
30 { 
31  for (int j = 0; m[i] < m[j] && m[j] != 0; j++) 
32  { 
33  product = product + (m[i] * n[j]); 
34  } 
35 } 
36 
37 cout << "lowerCount " << lowerCount << "\n"; 
38 cout << "equalCount " << equalCount << "\n";` 
39 cout << "higherCount " << higherCount << "\n"; 
40 cout << "product " << product << "\n""; 
+0

我的魔球沒有顯示m [i]和m [j]的值:( – 2013-04-24 13:22:00

+1

我只需要計算增長率,我沒有m [i]和m [ j]對不起:( – 2013-04-24 13:24:18

+0

希望你找到正確的答案,除此之外;) – 2013-04-24 13:31:51

回答

2

我認爲你正在尋找的答案是O(N^2 + 2N /(1/2N)+ 3n^3)如果你使用鮑爾默算法來計算複雜性,這是很清楚的。

+0

你能解釋一下你如何以此結束?而不是2N /(1/2N)= = 4N – 2013-04-25 07:19:03

1

據我所知,計算算法複雜度時,你可以給大O最佳,最壞和平均情況。

對於兩個嵌套循環,最好的情況是O(n) - 如果內部循環只執行一次(我忽略了兩個循環只處理一次迭代的事實)。 最糟糕的是O(n * k) - 第一個循環迭代n次,內部迭代k次。

Asier讓我們難過,我們不知道m [i]是什麼,所以不知道平均複雜度會是多少。

+0

然後我們可以更新我們的魔球 – 2013-04-24 13:29:18