算法之时间复杂度简析

www.allocmem.com · · 533 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

算法之时间复杂度简析

前言

    最近准备对算法进行一些系统的总结和学习,不积跬步无以至千里,不积小流无以成江海.此文主要对时间复杂度进行简单梳理和个人总结,本人才疏学浅,有所疏漏在所难免,如有不当和错误之处,欢迎指正

时间复杂度的定义(Time Complexity)

    时间复杂度,用简单地话描述为:为了大概估算程序运算时间的一种概量。那用什么来估算的呢?用简单的程序执行代码的次数,如int a = 3执行一次,一个n此的for循环表示执行n次等等。广义的T(n)表示在一个完全理想状态的计算机中程序所执行的实际指令次数,下面会提到的O(n)大O(Big Oh),Ω(omega),Θ(Theta) 都是对T(n)的一个大略估算抽象而来,这里先说明一下个人理解的精确度大小为:T(n)>Θ(Theta)>Ω(omega);Θ(Theta)比Ω(omega)更能确定次数范围。而这集中表示方法,都是基于Big-oh(大O表示法)。

大O表示法简析

    O(f(n))就是大O表示法,里面是一个表达式,可以看成是某一算法所需执行时间始终不会超过某一常数倍的f(n)。严格定义为:存在两个正常數c和n0,若n≥n0时T(n)≤cf(n),则记为T(n) = O(f(n))。f(n)又可以称为执行时间的成长率(rate of growth),结合上面可以看出,常用的大O时间复杂度的估算比真实的次数大(毕竟几乎都会有其他时间消耗),

大O表示法的常用计数方法(根据程序对n的大小对程序执行次数估算(大O法)走势进行判断)

  1. O(1)或O© 常数时间

    如普通的一行代码

  2. O(n) 线性时间

    int count = 1;
    while(count < n){
        count = count + 2;
        //其他时间复杂度为O(1)的代码 
        //如果使用常数时间只是把问题减少一个常数(如将问题减少1),那么这种算法就是 O(N)
    }
    

    执行n次,线性增长,一个n次的for循环也是O(n)

  3. O(log2n) 次线性时间 如:

    int count = 1;
    while(count < n){
        count = count * 2;
    //其他时间复杂度为O(1)的代码 
    }
    //如果一个算法用常数时间(O(1)将问题的大小削减为其一部分(通常是1/2),那么该算法就是 O(log N)
    

    比线性时间增长慢,所以叫次线性时间,二分法的时间复杂度也是O(log2n)。

  4. O(n2) 平方时间 如两层循环n次的for循环

  5. O(2^n) 指数时间

  6. O(n1og2n) 其他多项式时间 注:常见的算法时间复杂度由小到大依次为(n较大时):O(1)(log2n)(n)(n log2 n)(n^2)(n^3)(2^n)

Ω(omega)表示法定义

    Ω(g(n))也是类似大O法的时间渐进表示法,先说下严格定义:存在两个正常數c和n0,若n≥n0时T(n)≥cf(n),则记为T(n)= Ω(g(n));和大O表示法进行对比得出,Ω表示法渐进的时间复杂度比真实的小。

Θ(Theta)表示法定义

    Θ(Theta)表示法比上面两种都要精确,第一种严格定义为:当且仅当T(n) = O(h(n)),T(n) = Ω(h(n)),则T(n)=Θ(h(n)),这里理解为此时的渐进时间复杂度的两种算法重叠,前两中表示法和T(n)相等,则此时的h(n)就是T(n)=Θ(h(n))。

++下面引用下个人觉得对Θ(Theta)的不错的定义和理解,引用自market.cloud++

定义:f(n)=Θ(g(n)),若且唯若存在大于0的常數c1,c2和n0,使得对所有n值而言,n≧n0时,c1g(n)≦f(n)≦c2g(n)均成立。事实上f(n)=Θ(g(n)),就是g(n)可同时代表f(n)的上限和下限。以3n+2的例子说明

  • 当n≧2时,3n+2≦4n即3n+2=O(n)
  • 当n≧l时,3n+2≧3n即3n+2=Ω(n)
  • 则我们就可以做成以下的结论3n+2=Θ(n)。

补充(引用自数据结构和算法分析第二版)

    如果用传统的不等式来计算增长率,那么大O法表示T(n)的增长率小于等于f(n)的增长率, Ω中T(n)的增长率大于等于g(n)的增长率,Θ中T(n)的增长率等于h(n)的增长率

参考

《数据结构和算法分析第二版》

本文来自:www.allocmem.com

感谢作者:www.allocmem.com

查看原文:算法之时间复杂度简析

533 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传