内容简介：为什么需要复杂度分析？有两种估算方法：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 里的简易算法和数据结构之复杂度
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
The Four
Scott Galloway / Portfolio / 2017-10-3 / USD 28.00
NEW YORK TIMES BESTSELLER USA TODAY BESTSELLER Amazon, Apple, Facebook, and Google are the four most influential companies on the planet. Just about everyone thinks they know how they got there.......一起来看看 《The Four》 这本书的介绍吧!
