algorithm - 嵌套 for 循环的运行时复杂度

Question

for(a = c; a > 0; a/=2) 
    for(b=0; b < 2*a; b++)

我得出的结论是这是 O(nlogn) 运行时，但我不确定..我的逻辑是，最外层的 for 循环运行 logn 次，每次除以 2，然后最内层的 for 循环运行减半数的 2 倍；因此它运行了 n 次。

Answer 1

#include <iostream>

int main() {

    int c = 16;

    for(int a = c; a > 0; a/=2) {

        for(int b =0; b < 2*a; b++)
            std::cout << "*";

        std::cout << std::endl;
    }
}

输出

********************************
****************
********
****
**

• 在你看到的第一个内循环中，b 从 0 到 2*a
• 在你看到的第二个内部循环中，b 从 0 到 2*(a/2)
• 在你看到的第三个内部循环中，b 从 0 到 2*(a/4)

求和:2a + a + a/2 + ...+1 = 2a -1\in O(n)，因为输入大小。