-3

我必须分析以下代码片段的大 O 复杂性：

一个）

// loop 1
for(int i = 0; i < n; i++)
  // loop 2
  for(int j = i; j < n; j++)
    sum++;

b)

// loop 1
for(int i = 0; i < n; i++)
  // loop 2
  for(int j = i + 1; j > i; j--)
    // loop 3
    for(int k = n; k > j; k--)
      sum++;

我不知道该怎么做，提供的任何帮助将不胜感激。谢谢。

4

2 回答 2

3

要分析 Big-Oh 复杂性，您必须尝试计算代码执行了多少基本操作。

在您的第一个循环中：

for(int i = 0; i < n; i++)
    for(int j = i; j < n; j++)
        sum++;

调用了多少次sum++？第一个循环发生n了多次，而在每一个循环中，第二个循环都发生了n多次。这为您提供了围绕n*n的操作，这相当于O(n^2).

我会让你解决第二个问题。

于 2012-10-21T09:30:19.797 回答
1

第一个是直截了当的（使用第二个代码快照的工具，这有点棘手） - 我将专注于第二个代码快照。

大 O 表示法为算法执行的操作数提供了渐近上限。

让我们假设每个内部迭代都执行 1 个操作，让我们忽略计数器和循环的开销。
表示T(n)程序中完成的操作总数。

很明显，该程序没有更多的操作：

 // loop 1
for(int i = 0; i < n; i++)
   // loop 2
   for(int j = i+1; j > i; j--) //note a single op in here, see (1) for details
      // loop 3
      for(int k = n; k > 0; k--) //we change k > j to j > 0 - for details see (2)
         sum++;

(1) 由于j被初始化为i+1, 并且每次迭代都减少, 在 loop2 的第一次迭代之后, 你将得到j == i, 并且条件将产生 false - 因此 - 完成了一次迭代 (
2) 原始循环不再迭代n(since j >= 0) - 因此“新程序”比旧程序“不是更好”（就上限而言）。

简化程序
的复杂度 上述程序的总复杂度为O(n^2)，因为 loop1 和 loop3n各重复一次，而 loop2 只重复一次。
如果我们假设每个内部循环都执行单个命令 - 那么执行的命令总数是n^2.

结论：
由于新程序正在执行n^2“操作”（根据假设）并且原始程序“并不比新程序差” - 它正在执行T(n) <= n^2步骤。
根据大 O 表示法的定义（c=1，并且对于每个 N）-您可以得出结论，该程序是O(n^2)

于 2012-10-21T09:51:57.353 回答