数据结构入门

数据结构

复杂度分析

大O表示法

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

复杂度分析法则

• 单段代码看高频：比如循环
• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度
• 嵌套代码求乘积：比如递归、多重循环等
• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加

常用的复杂度级别

• 多项式阶（随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长）

  • O(1)（常数阶）
  • O(logn)（对数阶）
  • O(n)（线性阶）
  • O(nlogn)（线性对数阶）
  • O(n^2)（平方阶）
  • O(n^3)（立方阶）

• 非多项式阶（随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差）

  • O(2^n)（指数阶）
  • O(n!)（阶乘阶）

复杂度分析的4个概念

• 最好情况时间复杂度

  • 在最理想的情况下，执行这段代码的时间复杂度

• 最坏情况时间复杂度

  • 在最糟糕的情况下，执行这段代码的时间复杂度

• 平均情况时间复杂度

  • 用代码在所有情况下执行的次数的加权平均值表示

• 均摊时间复杂度

  • 在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。