c - 时间复杂度和代码输出

Question

我很难分析以下代码的时间复杂度和输出。我什至连输出都找不到。这个我知道

1<< N

左移 1 N 位。

#include <stdio.h>
#define N 3
int main() {
 int array[N] = {1,2,3};
 int i,j;
 for ( i=1; i<(1<<N); i++) {
      for( j=0; j<N; j++) {
           if((1<<j)&i) {
                printf("%d", array[j]);
           }
      }
      printf("\n");
 }
 return 0;
}

• Q1) if 在此 c 程序实例中成功执行了多少次。 N=n时有多少次，n为正整数？
• Q2) 输出是什么？换句话说，执行是如何发生并最终到达输出的。简而言之 - 如何获得输出？
• Q3) 当N很大时，复杂度是多少

我尝试过的

当 N=3 时，

1<<N

将是 8 所以外循环执行 8 次，内循环执行 3 次

但是怎么办

if((1<<j)&i) 

有效吗？

当 N 为 n 时，正整数我认为复杂度为 O(n 2^n)

请帮我分析一下程序的代码和复杂度

Answer 1

关于外循环和 if 的迭代次数，您的分析大部分是正确的测试。只要N是这样的 1 << N不会导致溢出(从而调用未定义的行为)，if执行了 N * (2^N - 1) 次。

问题 Q1 更微妙:if 重复了多少次？对任意正整数执行成功？

• 语言律师会说if只要不调用未定义的行为，就会成功执行。也就是说:只要n < CHAR_BIT * sizeof(int) - 1 .确实为大N , (1 << N)调用未定义的行为，因为它会导致算术溢出。例如，如果键入 int是 32 位宽，1 << N 的最大值定义为 30 .
• 问题可能指的是条件:测试评估为非零值的次数有多少？外部循环使用 N 遍历所有非零数字位或更少。内部循环遍历所有位号，对每个位测试一次。总数if测试是 n * 2ⁿ - n。每个位都针对每种可能的组合进行测试:一半的测试评估为 0和一半到非零，而 n 测试值 0被省略。问题 Q1 的答案是 n * 2^n-1 - n，可以分解为 n * (2^n-1 - 1)。

一半的测试成功并调用printf() .简化可忽略的值和常数因子 2，对于较大的 n 值，该函数的时间复杂度为 O(n * 2ⁿ) .