数据结构与算法之复杂度

事后统计法:

  • 把代码跑一边,通过监控、统计就能得到算法执行时间和占用内存大小。
  • 局限性:
    1. 测试结果很依赖测试环境
    2. 测试结果受数据规模影响很大

渐进时间复杂度:

  • 代码执行时间随数据规模增长的变化趋势,简称时间复杂度
    • 只关注循环执行次数最多的一段代码
    • 加法法则:总复杂度等于量级最大的那段代码的复杂度
    • 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

大O表示法:

  • 算法执行时间与每行代码执行次数成正比,用 T(n) = O(f(n)) 表示,其中 T(n) 表示算法执行时间,f(n) 表示每行代码执行总次数,而 n 往往反映的是数据规模。

复杂度量级:

  • 多项式量级:
    • 常数阶O(1)
    • 对数阶O(logn)
    • 线性阶O(n)
    • 线性对数阶O(nlogn)
    • 方阶O(n^k)
  • 非多项式量级:
    • 指数阶O(2^n)
    • 阶乘阶O(n!)

线性对数阶: 对数之间可以相互转换,如:logn = Clogk 3 ,所以可以统一用 logn 表示

渐进空间复杂度:

  • 算法存储空间与数据规模之间的增长关系,简称空间复杂度
  • 常见空间复杂度
    • O(1)
    • O(n)
    • O(n^2)

复杂度分析的4个概念

  • 最好情况时间复杂度:代码在最理想情况下执行的时间复杂度。
  • 最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
  • 平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。
  • 均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

为什么要引入这4个概念?

  1. 同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。
  2. 代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

Larwas
请先登录后发表评论
  • latest comments
  • 总共0条评论