Please enable JavaScript.
Coggle requires JavaScript to display documents.
数据结构与算法 (复杂度分析 (大O复杂度表示法 (时间复杂度分析 (只关注循环次数最多的那段代码, 总复杂度等于量级最大的那段代码的复杂度,…
数据结构与算法
复杂度分析
通过统计，监控实际程序执行的情况就可以知道程序的性能(事后统计法)，为什么需要复杂度分析？
事后统计法依赖外部环境，比如硬件，数据数量，不同的情况可能有不同的结果。
大O复杂度表示法
例子：
T(n)=O(n)
T(n) = O(n2)
时间复杂度分析
只关注循环次数最多的那段代码
总复杂度等于量级最大的那段代码的复杂度
嵌套代码的复杂度等于嵌套代码内外复杂度的成绩
常见复杂度量级
多项式量阶
线性阶:O(n)
指数阶:O(ln)
线性对数阶
平方阶，立方阶，k次方阶
常量阶 O(1)
不存在循环语句、递归语句
非多项式量阶
阶乘阶
对数阶
为什么学？
可以写出性能好的代码
算法，解决问题的思路和方法，可以用到生活和事业中
有效训练大脑思考能力的方式之一
广义上讲：
数据结构： 存放数据的存储结构
算法： 操作数据的方法
侠义上讲：
指哪些著名的存储结构和算法。如队列，堆，栈，二元查找和动态规划。
数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Tree
算法：
递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法