这个程序的复杂性是什么？

Question

我一直在寻找如何计算算法复杂度的方法。虽然有一些很好的解释，但我似乎并不完全理解它是如何工作的。所以我想也许在这个例如，有人可以为我澄清一下

void test(int n){
for ( int i = 1; i <= n; i++, n=n/2)
    for(int j = 1; j <= n; j++)
       ..O(1)..
        }

Answer 1

第一次外循环运行s，内循环会运行n次。
第二次外循环运行s，内循环会运行n/2次。
第三次外循环运行s，内循环会运行n/4次。
第四次外循环运行s，内循环会运行n/8次。
. . .
最后一次外循环运行s，内循环会运行1次。

当你对你得到的系列求和时

n + n/2 + n/4 + n/8 + ... = 2n

内层循环体一共执行了2n次，所以算法的复杂度为O(n)。