程序或算法的时间复杂度

  • 一个程序或算法的时间效率,也称“时间复杂度”,有时简称“复杂度”
  • 复杂度常用大写字母 O 和小写字母 n 来表示,比如 O(n), O(n²)等。n代表问题的规模
  • 时间复杂度是用算法运行过程中,某种时间固定的操作需要被执行的次数和n的关系来衡量的,在无序数列中查找某个数,复杂度是O(n)
  • 计算复杂度的时候,只统计执行次数最多的(n足够大时)那种固定操作的次数。比如某个算法需要执行加法n²次,除法n次,那么就记其复杂度是 O(n²)
  • 复杂度有"平均复杂度""最坏复杂度"两种,两者可能一直,也可能不一致
  • 如果复杂度是多个n的函数之和,则只关心随n的增长增长的最快的那个函数

    • O(n³+n²) => O(n³)
    • O(2^n+n³) => O(2^n)
    • O(n!+3^n) => O(n!)
  • 常数复杂度:O(1)
  • 对数复杂度:O(log(n))
  • 线性复杂度:O(n)
  • 多项式复杂度:O(n^k)

k是一个常数

  • 指数复杂度:O(a^n)
  • 阶乘复杂度:O(n!)

常见的一些算法复杂度:

exp.png

本文链接:

http://godrry.com/archives/time-complexity-of-a-program-or-algorithm.html
1 + 1 =
沙发还热乎呢~