0

基本上，我正在努力掌握操作计数和 Big-O 符号。我知道这可能是计算机科学中最难理解的部分之一，我不得不承认我正在为此苦苦挣扎。谁能给我一些关于这些例子的帮助，可能还有关于 Big-O 的任何进一步的帮助/链接？

for (i = 0; i < N; i++)
     { for (j = i; j < N; j++)
          { sequence of statements }
     }

在这里我会说复杂度是 O(N²) - 二次

int m = -9
for (j = 0; j < n; j+=5)
     {
     if (j<m)
          {
          for (k = 1; k <n; k*=3)
               {some code}
               }
     }

这里我还要说是 O(N²)。第一个循环需要 N，第二个循环需要 N，所以我会说答案是 O(N*N)，它等于 O(N²)。

任何有助于进一步理解的帮助和建议都会很棒！

4

5 回答 5

2

正如您所怀疑的那样，第一个确实是O(n^2)假设“语句序列”是O(1)。

但是，代码的第二部分是O(n)，因为j < m从未满足条件 - 因此，外循环仅迭代自身而实际上什么也不做。内部循环甚至无法到达。

作为旁注，一些编译器实际上可能O(1)仅通过设置变量的最终值来优化要运行的代码的第二部分，但这不是问题的重点。

于 2013-08-15T17:25:13.213 回答
1

第二个例子是复杂性O(N)。

int m = -9
for (j = 0; j < n; j+=5)
{
    if (j<m)
    {
        // this never executes; m is negative and j is positive
    }
}
于 2013-08-15T17:27:41.130 回答
0

好的，另外一点，我真的建议您在算法介绍系列中进行一次讲座。相信我，你不需要再看下去了。 http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

于 2013-08-16T13:15:31.000 回答
0

只是在这里抛出这个：如果我们假设该j<-9子句是一个错误并忽略它，那么您的第二个示例有两个嵌套循环。然而，内循环实际上是乘以 k3。所以这使得这个内循环 O(log n)。这使得这对循环为 O(n log n)。我不确定这是不是答案，但你要求进一步理解，所以......你知道......也许这更进一步。

于 2013-08-15T21:01:34.090 回答
0

第一个示例：当 i = 0 时，内部循环执行 N 次，当 i = 1 时执行 N-1 次，依此类推……您只需计算 for 循环执行的步数

(N) + (N - 1) + (N - 2) + ... + 2 + 1

步数 = N(N+1)/2 = (N^2 + N) / 2

  1. N <=> 1 |从左到右| => N+1
  2. (N - 1) <=> 2 |从左到右| => N+1
  3. (N - 2) <=> 3 |从左到右| => N+1 。. . ñ

大O国家是什么意思？

F(N) = O(G(N)) 表示 |F(N)|<= c*|G(N)| 其中 c > 0

这意味着 G(N) 函数是函数增长率的上限。F(N) 不能比 G(N) 增长得更快。

于 2013-08-15T17:45:21.737 回答