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"";
4

2 回答 2

2

我认为您正在寻找的答案是 O(N^2 + 2N / (1/2N) + 3n^3) 如果您使用鲍尔默斯算法来计算复杂性，这很明显。

于 2013-04-24T15:11:40.557 回答
1

据我所知，在计算算法复杂度时，您可以给出最佳、最坏和平均情况的大 O。

在两个嵌套循环的情况下，最好的情况是 O(n) - 如果内部循环只执行一次（我忽略了两个循环可能只处理一次迭代的事实）。最糟糕的是 O(n*k) - 第一个循环迭代 n 次，内部循环迭代 k 次。

Asier 很伤心，我们不知道 m[i] 中有什么，所以不知道平均复杂度是多少。

于 2013-04-24T13:28:15.977 回答