数据结构和算法
2018-10-24 本文已影响0人
默云客
数据结构和算法知识栈
▷ 复杂度分析
用数据结构和算法来解决问题，解决的好不好，效率高不高，省不省空间，这个用形容词是没法描述的，必须用定量的指标来分析，这就会用到贯穿整个数据结构和算法的“复杂度分析”。一般分为时间复杂度和空间复杂度。
大O复杂度表示法
假设每行代码语句执行的时间是一样的，不论有多少行代码，同一行代码执行多少次，那么，可以得到一个简单的规律，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。总结成一个公式，即：T(n) = O(f(n))。
其中，T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。这就是大O时间复杂度表示法。
时间复杂度
- 大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，也叫做渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
- 当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：
；
。
- 分析方法：
- 关注循环次数最多的代码
大O复杂度表示法，只是表示一种变化趋势，忽略掉公式中的常量、低阶和系数，只需要记录一个最大阶的量级。记录下来循环次数最多的代码的量级，就是整段要分析代码的时间复杂度。 - 加法法则：总复杂度等于量级最大的那段代码的复杂度
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
- 关注循环次数最多的代码
- 复杂度量级：
前5种为多项式量级，后两种为非多项式量级和
，当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
- 常量阶：
;
O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1) - 对数阶：
;
对数阶时间复杂度非常常见，同时也是最难分析的一种时间复杂度。
i=1;
while (i <= n) {
i = i * 2;
}
如以上代码，每执行一次，i乘以2，最后执行次数就是,这段代码时间复杂度就是
,而对数之间是可以互相转换的，
就等于
*
,其中
是一个常量,所以，
。因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为
- 线性阶：
;
线性阶时间复杂度要灵活计算，如果两个规模不一样大小的循环，时间复杂度不能简单表示为其中一个，就会有加法或乘法，如、
- 线性对数阶：
;
线性对数阶就是将对数阶循环了n次，如归并排序、快速排序的时间复杂度都是 - 平方阶：
; 立方阶：
; ……K次方阶：
；
- 指数阶：
- 阶乘阶：
- 常量阶：
空间复杂度
空间复杂度全称就是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
我们常见的空间复杂度就是 、
、
，像
、
这样的对数阶复杂度平时都用不到。空间复杂度分析比时间复杂度分析要简单很多。
