algorithm - 程序复杂度类

Question

基本上，我很难掌握操作计数和大 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²)。

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

Answer 1

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

然而，代码的第二部分是O(n) , 因为条件 j < m永远不会满足 - 因此，外循环只会迭代自己而实际上什么都不做。内环甚至无法到达。

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