设为首页 加入收藏

TOP

算法时间复杂度的计算(一)
2013-11-20 14:18:52 来源: 作者: 【 】 浏览:1747
Tags:算法 时间 复杂度 计算

    基本的计算步骤
    时间复杂度的定义
    一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。
    根据定义,可以归纳出基本的计算步骤
    1. 计算出基本操作的执行次数T(n)
    基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。
    2. 计算出T(n)的数量级
    求T(n)的数量级,只要将T(n)进行如下一些操作:
    忽略常量、低次幂和最高次幂的系数
    令f(n)=T(n)的数量级。
    3. 用大O来表示时间复杂度
    当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。
    一个示例:
    (1) int num1, num2;
    (2) for(int i=0; i<n; i++){
    (3)     num1 += 1;
    (4)     for(int j=1; j<=n; j*=2){
    (5)         num2 += num1;
    (6)     }
    (7) }
    分析:
    1.
    语句int num1, num2;的频度为1;
    语句i=0;的频度为1;
    语句i<n; i++; num1+=1; j=1; 的频度为n;
    语句j<=n; j*=2; num2+=num1;的频度为n*log2n;
    T(n) = 2 + 4n + 3n*log2n
    2.
    忽略掉T(n)中的常量、低次幂和最高次幂的系数
    f(n) = n*log2n
    3.
    lim(T(n)/f(n)) = (2+4n+3n*log2n) / (n*log2n)
    = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3
    当n趋向于无穷大,1/n趋向于0,1/log2n趋向于0
    所以极限等于3.
    T(n) = O(n*log2n)
    简化的计算步骤
    再来分析一下,可以看出,决定算法复杂度的是执行次数最多的语句,这里是num2 += num1,一般也是最内循环的语句。
    并且,通常将求解极限是否为常量也省略掉?
    于是,以上步骤可以简化为:
    1. 找到执行次数最多的语句
    2. 计算语句执行次数的数量级
    3. 用大O来表示结果
    继续以上述算法为例,进行分析:
    1.
    执行次数最多的语句为num2 += num1
    2.
    T(n) = n*log2n
    f(n) = n*log2n
    3.
    // lim(T(n)/f(n)) = 1
    T(n) = O(n*log2n)
    --------------------------------------------------------------------------------

     

首页 上一页 1 2 3 4 5 6 7 下一页 尾页 1/21/21
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇求二叉树两结点最小公共祖先 下一篇C语言指针类型、指针大小

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: