数据结构与算法之复杂度
事后统计法：
- 把代码跑一边，通过监控、统计就能得到算法执行时间和占用内存大小。
- 局限性：
- 测试结果很依赖测试环境
- 测试结果受数据规模影响很大
渐进时间复杂度：
- 代码执行时间随数据规模增长的变化趋势，简称时间复杂度
- 只关注循环执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
大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个概念？
- 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述代码的时间复杂度，所以引入这4个概念。
- 代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。
本文为Larwas原创文章,转载无需和我联系,但请注明来自larwas博客 https://larwas.com
- 上一篇： phpstrome 导入/出配置菜单消失问题
- 下一篇： 数据结构与算法之数组
请先登录后发表评论
- latest comments
- 总共0条评论
最新评论