求下述伪代码的时间复杂度：已知外层循环为log n次，需解析内层及整体复杂度

先给出待分析的伪代码：

void buzz(int num, int [] a)
{
    for(int i=1;i<num;i*=2){
      for(int j=0;j<a[i]%num;j++){
          print(num);
      }
    }
}

内层循环的时间复杂度 #

内层循环的迭代次数由a[i] % num的结果决定：

• 取模运算的结果范围是 0 ≤ a[i]%num < num，因此单个内层循环的最坏时间复杂度为O(num)（当a[i]%num取到最大值num-1时）。
• 最好情况是O(1)，当a[i]%num=0时，内层循环直接跳过，不执行任何操作。

由于数组a的元素值是输入变量，没有额外约束时，我们通常基于最坏情况进行复杂度评估。

整体时间复杂度 #

已知外层循环的执行次数为O(log num)（i从1开始每次翻倍，直到i≥num，迭代次数为对数级）：

• 最坏情况下，每次内层循环都达到O(num)的执行次数，因此整体时间复杂度为O(num × log num)。
• 如果a的元素满足特定约束（比如所有a[i]%num都是常数或O(1)级别的值），整体复杂度会降至O(log num)，但这属于特殊场景。

内容的提问来源于stack exchange，提问作者Nick