当前位置：首页 → 问答吧 → 请教一道搜狗笔试题——计算算法的复杂度

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

时间：2011-09-18

来源：互联网

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

作者: qianshe223 发布时间: 2011-09-18

不懂,帮顶

作者: JayYounger 发布时间: 2011-09-18

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!)

没学过《算法》，不知道是不是这样分析是否正确？

作者: bao110908 发布时间: 2011-09-18

应该是根一个数列求和一样的，只是这个数列里面的每个元素也是一个数列。。我是这么理解的。不知道有没有帮到你，呵呵。

作者: yexiongMYBH 发布时间: 2011-09-18

引用 2 楼 bao110908 的回复:

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!)

没学过《算法》，不知道是不是这样分……

谢谢火龙果的解析，照这样的话，那这个小算法的复杂度十分高啊。

作者: qianshe223 发布时间: 2011-09-18

算法复杂度是《数据结构》中讲的，有点印象，但忘记的差不多了，应该不像2楼说的那样。
楼主可以参考下面的研究下：
http://blog.csdn.net/popkiler/article/details/2110144

作者: DriftKing 发布时间: 2011-09-18

引用 4 楼 qianshe223 的回复:

引用 2 楼 bao110908 的回复:

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……

这个效率比 N(lgN) 稍微小一些，应该算是很低的了。

作者: bao110908 发布时间: 2011-09-18

算法中 O(N*lg(N)) 与 O(lg(N!)) 是一样的，呵呵，详见：

http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

O(N*lg(N)) 算法效率的算法有：快速傅立叶变换；堆排序、快速排序、归并排序等排序算法。

作者: bao110908 发布时间: 2011-09-18

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).

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

作者: daijope 发布时间: 2011-09-18

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

热门阅读

热门下载