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