时间复杂度 - 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，我迭代 100 次 + 1 用于最后一次检查 第二次迭代 m = 50：循环 运行 50 次，我迭代 50 次 + 1 次用于最后一次检查 .....等等

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

Answer 1

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

---

注意 - 如果我们在内部循环中将 i < m 替换为 i < n，我们将获得 O(n*log(n)) 复杂度，因为在这种情况下我们有 n + n + n +.. + n 内部循环操作循环，其中加数为 log(n)