请教一道搜狗笔试题——计算算法的复杂度
去搜狗参加了一下笔试面试，被鄙视了。。。
有一道分析算法复杂度的问题，我一直都不咋会分析算法复杂度，看到就懵了，没做。
回来求教一下版上的大虾，求指教算法复杂度的计算方式，尤其是递归算法！！！
题目：
分析给定代码的时间复杂度。

C/C++ code

void foo();
void bar(int k){
    if(k>0){
        do{
            k=k/2;
                        bar(k);
                }while(k)
        }else{
         foo();
        }
}
void xxx(int n){
    for(int i=1;i<n;i+=i){
         bar(i);
        }
}

分析xxx函数的复杂度是多少。




------解决方案--------------------
bar 的循环次数是 lgN（lg 表示以 2 为底的对数）
xxx 的执行的次数就是每个 bar 的次数相加，即：

1 + lg(2) + lg(3) + lg(4) + ... + lg(N)
= 1 + lg(2 * 3 * 4 * .. * N)
= 1 + lg(N!)

因此 xxx 的复杂度（忽略常数项）是 lg(N!)

没学过《算法》，不知道是不是这样分析是否正确？
------解决方案--------------------
i+=i相当于i = i*2;这样的话，xxx最外面的时间复杂度是log(n)。
里面 k=k/2;时间复杂度也是log(n)。但是还有递归调用,k的值只有2/k 也就是log（n/2）,log(n/2) = long(n) - 1;

也就是说bar的时间复杂度是：(1 + 2 + 3 + .. + log(n)) + (1 + 2 + 3 + ... + (log(n) - 1)) + (1 + 2 + 3 + ...+ (log(n) - 2)) + ... + 1;

上面的计算一下就是：（1 + log(n)）(log(n)/2 + （1 + log(n)）(log(n)/2 - 1 + （1 + log(n)）(log(n)/2 - 2 + ... + 2 + 1;

也就是：((1 + log(n))(log(n)/2 + 1)（1 + log(n)）(log(n)/4;

化简一下时间复杂度就是O（ log(n)^4）

在加上外面一层的log(n)，所以总的时间复杂度应该是O(log(n)^5).

这只是我自己的想法，不知对不对，希望不要误导别人了。

------解决方案--------------------
可以先求下bar(n）的复杂度：
另T(n）为bar(n)的复杂度，可以推出T(n)=2*T(n/2) ==> bar(n)的复杂度为O(n)。
结果就是O(n) + 0(n/2) + O(n/4) +...+O(1) = O(n)
 
所以我觉得是O（n），轻拍，各位大牛~

------解决方案--------------------
看下面这段展开do{}while循环的第一次循环，明显bar(n)相当于调用了两次bar(n/2)，因此T(n)=2*T(n/2是正确的。

void bar(int n){
if(n>0){
k = n/2;
bar(k); // 第一次bar(n/2)

// 余下这些也相当于调用bar(n/2)一次
do{
k=k/2;
bar(k);
}while(k);

}else{
foo();
}
}
------解决方案--------------------
令T(n）为bar(n)的复杂度，可以推出T(n)=2*T(n/2)？可令循环展开
void bar(int n)
{
if(n>0){
k = n/2;
bar(k); // 第一次bar(n/2)
// 余下这些也相当于调用bar(n/2)一次
do{
k=k/2; bar(k);
}while(k);
}else
{
foo();
} 
}

èbar(n) = bar(n/2)+bar(n/4)+…+bar(1) A
èbar(n/2) = bar(n/4)+…+bar(1) B
A-B è bar(n/4)+…+bar(1) = bar(n/2) C
C带入Aè bar(n) = 2*bar(n/2) D
由Dè bar时间复杂度0(n) E

XXX的复杂度 = o(n)+o(n/2)+…+0(1), 不妨设0(n)运算次数为2^K
2^K + 2^(K-1)+…+2^0 = 2^(k+1)-1≈2*o(n), 所以XXX的时间复杂度为o(n)

转载自我一同学。