c++ - 我如何找到这段代码的时间复杂度(Big O)？

Question

我试图理解这个 O 符号是如何工作的，我在下面有一段代码，在每行旁边我都会有一个我认为时间复杂度的评论。如果我错了，请纠正我并解释为什么我的逻辑不正确。

代码 #1

for (int i = 0; i < n; i++) <<<<<<<<<<<<<<<<<<< O(1)*O(N)
 {
    for (int j = 0; j < 3; j++) <<<<<<<<<<<<<<< O(1)*O(1)
      {
        for (int k = 0; k < 3; k++) <<<<<<<<<<<<<<O(1)*O(1)
          {
            printf("%d", arr[i]); <<<<<<<<<<<<<<O(1)
           }
        printf("\n"); <<<<<<<<<<<<<<<<<<O(1)
    }

}

运行时间 = O(N)，在将所有内容加起来之后。

代码 #2

for (int i = 2; i <= n; i++) <<<<<<<<<<<<O(1)*O(N)
{
        int j;<<<<<<<<<<<<<<<<<<<<<<<O(1)
        printf("\n%d:", i);<<<<<<<<<<<<<<O(1)
        for(j = 2; j <= i; j = j * 2) <<<<<<<<<<<O(n-2)??????????
        {
            printf("%d ", j);<<<<<<<<<<<<<<O(1)
        }
         printf("\n%d:", i);<<<<<<<<<<<<<<<<<<<<O(1)
         for(int k = j/2; k >= 2; k = k / 2)<<<<<<<<<<<<<I am not sure of this one
        {
             printf("%d ", k);
        }
  }

运行时间:不确定..

总的来说，我有点明白了，但仍然不完全确定在某些情况下如何使用它。是否还有其他人有指南或某种形式来举例说明 for 循环和 while 循环的时间复杂度？

Answer 1

k的 block 是O(lg j)，其中j是O(n)，所以k是O(lg n)。但是如果你考虑整个程序，它是 O(n lg n)。