江苏龙网

  1. 主页 > 生活百科 > >

算法到底是什么？( 二 )

算法

  • T(n)=O(h(n))和T(n)=Ω(h(n))
  • T(n)=Ω(h(n))
    • 分析算法效率时，我们总是希望找到O
    O时最大的上界；找到Ω
    Ω时最小的下界 。
    下面三张图表示算法复杂度为不同函数时对应的耗时：
    算法到底是什么？

    文章插图
     

    算法到底是什么？

    文章插图
     

    算法到底是什么？

    文章插图
     
    综上：一个专业的程序，设计了一个O(N
    2
    )
    O(N2)的算法，应该本能的想到是否能把他改进为O(Nlog
    N
    )
    O(NlogN)的算法 。
    算法复杂度分析小窍门
    • 若两段算法分别有复杂度T
    • 1
    • (n)=O(f
    • 1
    • (n))
    • T1(n)=O(f1(n))和T
    • 2
    • (n)=O(f
    • 2
    • (n))
    • T2(n)=O(f2(n))，则
    • T
    • 1
    • (n)+T
    • 2
    • (n))=max(O(f
    • 1
    • (n)),O(f
    • 2
    • (n)))
    • T1(n)+T2(n))=max(O(f1(n)),O(f2(n)))
    • T
    • 1
    • (n)×T
    • 2
    • (n))=max(O(f
    • 1
    • (n)×f
    • 2
    • (n))
    • T1(n)×T2(n))=max(O(f1(n)×f2(n))
    • 若T(n)
    • T(n)是关于n
    • n的k
    • k阶多项式，那么T(n)=Θ(n
    • k
    • )
    • T(n)=Θ(nk)
    • 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
    • if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度，总体复杂度取三者中最大




    推荐阅读


    上一篇：天猫家装节什么时候 天猫双十一预售规则

    下一篇：最顶级的牛排级别 世界四大顶级牛排多少钱