内容简介：为什么需要复杂度分析？有两种估算方法：1.事后统计法 2.大O复杂度表示法时间复杂度分析
为什么需要复杂度分析？
有两种估算方法：1.事后统计法 2.大O复杂度表示法
- 事后统计法: 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小
- 测试结果非常依赖测试环境
- 测试结果受数据规模的影响很大
-
我们需要一个不用具体的测试数据来测试，就可以粗略的估计计算法的执行效率的方法——大O复杂度表示法
从CPU角度看，代码的执行类似这种操作：读数据——运算——写数据。
所有代码的执行时间T(n)与每行代码的执行次数n成正比。T(n)=O(f(n)),例：T(n)=O(2n+2),T(n)=O(2n²+2n+3)
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫，渐进时间复杂度，简称时间复杂度。T(n) = O(n)； T(n) = O(n²)。
时间复杂度分析
- 只关注循环执行次数最多的一段代码：核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度
- 加法法则：总复杂度等于量级最大的那段代码的复杂度
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
几种常见时间复杂度实例分析
常量阶O(1) 对数阶O(logn) 线性阶O(n) 线性对数阶O(nlogn) 指数阶O(2^n) 阶乘阶O(n!)
粗略分为两类：多项式量级和非多项式量级，非多项式量级只有两个：O(2^n)和O(n!)。
以上所述就是小编给大家介绍的《数据结构与算法1-复杂度分析1》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 算法与数据结构(一)：时间复杂度与空间复杂度
- 数据结构与算法系列（一）：时间复杂度和空间复杂度
- 《数据结构与算法之美》学习笔记之复杂度
- 数据结构与算法之美 - 时间和空间复杂度
- 数据结构与算法的重温之旅（二）——复杂度进阶分析
- [译] JS 里的简易算法和数据结构之复杂度
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
