当前位置: 代码迷 >> J2SE >> 请问一道搜狗笔试题——计算算法的复杂度
  详细解决方案

请问一道搜狗笔试题——计算算法的复杂度

热度:285   发布时间:2016-04-24 18:12:45.0
请教一道搜狗笔试题——计算算法的复杂度
去搜狗参加了一下笔试面试,被鄙视了。。。
有一道分析算法复杂度的问题,我一直都不咋会分析算法复杂度,看到就懵了,没做。
回来求教一下版上的大虾,求指教算法复杂度的计算方式,尤其是递归算法!!!
题目:
分析给定代码的时间复杂度。
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)

转载自我一同学。
  相关解决方案