内容简介：为什么需要复杂度分析？有两种估算方法：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 里的简易算法和数据结构之复杂度
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
计算机程序设计艺术
Donald E.Knuth / 黄林鹏 / 机械工业出版社 / 2010-8 / 69.00元
《计算机程序设计艺术(第4卷·第0册):组合算法与布尔函数概论(双语版)》是《计算机程序设计艺术，第4卷：组合算法》的第0册。《计算机程序设计艺术(第4卷·第0册):组合算法与布尔函数概论(双语版)》介绍了组合搜索历史和演化，涉及组合搜索技术的理论和实践应用，探究了布尔函数相关的所有重要问题，考察了如何最有效地计算一个布尔函数的值的技术。本册是《计算机程序设计艺术的》第7章，即组合搜索一长篇宏论的......一起来看看 《计算机程序设计艺术》 这本书的介绍吧!
