时间复杂度 - While 循环除以 2 并嵌套 for 循环

Question

我陷入了即将到来的期中考试的复习问题，非常感谢任何帮助。

请看下面的函数：

void george(int n) {                
    int m = n;                              //c1 - 1 step
    while (m > 1)                           //c2 - log(n) steps
    {                       
        for (int i = 1; i < m; i++)         //c3 - log(n)*<Stuck here>
          int S = 1;                        //c4 - log(n)*<Stuck here>
        m = m / 2;                          //c5 - (1)log(n) steps
    }
}

我陷入了内部 for 循环，因为每次迭代后 i 都在递增，并且 m 被除以 2。

如果 m = 100：第一次迭代 m = 100：循环将运行 100 次，i 迭代 100 次 + 1 用于最后一次检查 第二次迭代 m = 50：循环将运行 50 次，i 迭代 50 次 + 1 用于最后一次检查 .... 。 等等

由于 m 除以 2，这是否也被视为 log(n) ？

Answer 1

外部循环执行log(n)次数
内部循环执行n + n/2 + n/4 +..+ 1 ~ 2*n次数（等比级数和）
总时间为O(n + log(n)) = O(n)

注意 - 如果我们在内循环中替换i < mwith ，我们将获得复杂性，因为在这种情况下，我们有内循环的操作，其中被加数的数量是i < nO(n*log(n))n + n + n +.. + nlog(n)