计算算法复杂度的方法

代码示例：

void qingwa(int n)
{

    if(n!=0)
    {

        qingwa(n/2);
        printf("呱");
        qingwa(n/2);

    }
}

计算过程：

答案为O(n)

以下列代码为例：

f(n){
  f(n/2);
}

f(n)=f(n/2)+1;               // +1是因为循环执行次数为一次，正常情况下都是+1
f(n)=f(n/4)+2;
f(n)=f(n/2^k)+k;

k=log2(n);
f(n)=f(1)+log2(n)=log2(n)+1;

所以时间复杂度为log2(n)