[TOC]
数据结构和算法笔记
复杂度分析-上
如何分析、统计算法的执行效率和资源消耗
关键词
- unit_time: 假定每行代码执行时间为1个unit_time(单位时间)
- T(n): 所有代码的执行时间
- f(n): 代表每行代码执行的次数总和,因为这是一个公式，所以用 f(n) 来表示
- g(n): 代表自身封装的指定函数,复杂度分析并无此表达式.
- n: 数据规模的大小
- 大O: 代表公式中的代码执行时间T(n)和表达式f(n)成正比
提到数据结构和算法就不得不搞定时间复杂度和空间复杂度. 且复杂度分析是整个算法学习的精髓,只要掌握了复杂度分析,基本上就会了一半.
为啥要学习复杂度分析?
如果你觉得你完全可把代码跑一边测试一下来看看运行结果,那你的脑袋一定秀逗了.
其实这也是一种方法叫做:事后统计法,在万不得已的时候我也曾用过这种方式.
不过事后统计法有很多不便,比如:
- 太Low
- 费时费工
- 测试结果受到机器性能等其他环境的影响
- 测试结果结果受数据规模的影响
所以需要一个不需要进行数据测试,就能粗略估计算法效率的方法.也就是时间复杂度和空间复杂度分析.
大O复杂度表示法
算法的执行效率,其实就是代码的执行时间.
因为是估算,所以我们可以假设每行执行时间固定为unit_time.
分析代码,案例1:
int cal(int n) {
int sum = 0; //1个unit_time
int i = 1; //1个unit_time
for (; i <= n; ++i) { //n个unit_time
sum = sum + i; //n个unit_time
}
return sum;
}
那么上面代码中的2,3行分别执行1个unit_time也就是2unit_time,
4,5行执行n个unit_time也就是2n*unit_time,
所以这段代码的执行时间为: (2n+2)*unit_time
由此可见,所有代码的执行时间T(n)和每行代码的执行次数成正比.
分析代码,案例2:
int cal(int n) {
int sum = 0; //1个unit_time
int i = 1; //1个unit_time
int j = 1; //1个unit_time
for (; i <= n; ++i) { //n个unit_time
j = 1; //n个unit_time
for (; j <= n; ++j) {//n^2个unit_time
sum = sum + i * j; //n^2个unit_time
}
}
}
上面代码中2,3,4行分别执行1个unit_time也就是3unit_time,
5,6行分别执行n个unit_time也就是2n*unit_time,
7,8行分别执行n^2个unit_time也就是2n^2*unit_time
所以整段代码的执行时间为: T(n)=(3+2n+2n^2)*unit_time
综上所述,可见所有代码执行时间T(n)和每行代码的执行次数n成正比
总结公式-大O表示法: T(n)=O(f(n))
公式说明:
- T(n): 代码执行时间
- n: 数据规模的大小
- f(n): 每行代码执行的次数总和,因为这是一个公式，所以用 f(n) 来表示
- 大O: 代表公式中的代码执行时间T(n)和表达式f(n)成正比
综上所述,如果用大O表示法来表示的话:
- 案例1就是:
T(n)=O(2n+2), - 案例2就是:
T(n)=O(2n^2+2n+3)
这就是大O时间复杂度表示法.
注意: 大O时间复杂度并不表示具体代码的真正执行时间,而是表示代码执行时间随数据规模增长的变化趋势成正比.
所以,大O表示法也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度.
当n很大时,即使是100,1000,10000但在公式中的低阶,常量,系数,三部分并不左右增长趋势,所以直接忽略,只要记录一个最大的量级即可.
用大O复杂度表示法表示刚才两个案例: T(n)=O(n); T(n) = O(n^2)
时间复杂度分析
三个比较实用非分析方式:
- 只关注循环执行次数最多的一段代码
我们通常会忽略掉代码中的常量,系数,常量,只记录一个最大的量级.
所以,我们在分析代码的世界复杂度时,也只关注循环次数最多的一段代码.
这段核心代码执行的次数的n的量级,就是整段要分析代码的时间复杂度.
比如,代码分析案例1中的,2,3行代码就是常量级的执行时间与n的大小无关,对时间复杂度并没有影响.
循环次数最多的时4,5行代码,只分析这里两行即可,这两行代码分别执行了n次,所以代码分析案例1的时间复杂度就是O(n);
- 加法法则: 总复杂度等于量级最大的那段代码的复杂度
代码分析案例3:
int cal(int n) {
int sum_1 = 0;//1个unit_time
int p = 1;//1个unit_time
for (; p < 100; ++p) {//100个unit_time
sum_1 = sum_1 + p;//100个unit_time
}
int sum_2 = 0;//1个unit_time
int q = 1;//1个unit_time
for (; q < n; ++q) {//n个unit_time
sum_2 = sum_2 + q;//n个unit_time
}
int sum_3 = 0;//1个unit_time
int i = 1;//1个unit_time
int j = 1;//1个unit_time
for (; i <= n; ++i) {//n个unit_time
j = 1; //n个unit_time
for (; j <= n; ++j) {//n^2个unit_time
sum_3 = sum_3 + i * j;//n^2个unit_time
}
}
return sum_1 + sum_2 + sum_3;
}
第一段代码执行了100次,所以是一个常量级别的执行时间和n的规模无关.
第二段代码执行了O(n)次
第三段代码执行了O(n^2)次
总和三端代码的时间复杂度,取最大的量级.所以上面的代码的时间复杂度就是O(n^2).
也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。那我们将这个规律抽象成公式就是：
如果 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)))
- 乘法法则: 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
如果T1(n)=O(f(n))，T2(n)=O(g(n)) 那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
也就是, 假设 T1(n) = O(n)，T2(n)= O(n2)，那么 T1(n) * T2(n) = O(n3)
放到具体的代码上，可以把乘法法则看成是嵌套循环,下面来个代码案例说明一下
代码分析案例4:
int cal(int n) {
int ret = 0; //1个unit_time
int i = 1;//1个unit_time
for (; i < n; ++i) {//n 个unit_time
ret = ret + f(i); //假设f()函数没有循环,那么这里就是n个unit_time,但f()是n个unit_time,所以这里是n^2个unit_time
}
}
int f(int n) {
int sum = 0;//1个unit_time
int i = 1;//1个unit_time
for (; i < n; ++i) { // n个unit_time
sum = sum + i;// N 个unit_time
}
return sum;
}
分析cal()函数:
假设f()函数是一个没有循环的普通操作,那么cal()的4-6行的时间复杂度就是T1(n)=O(n)
但是f()函数本身的时间复杂度时T2(n) = O(n)
所以整个cal()函数的时间复杂度就是T(n)=T1(n)*T2(n)=O(n*n)=O(n^2)也就是T(n)=O(n^2)
常见时间复杂度
统计几个常见的复杂度量级,几乎可以涵盖今后可以解除到的所有带么的复杂度量级
- 指数阶 O(2^n)
- 阶乘阶 O(n!)
- 常量阶 O(1)
- 对数阶 O(logn)
- 线性阶 O(n)
- 线性对数阶 O(nlogn)
- 平方阶 O(n^2)
- 立方阶 O(n^3)
- K次方阶 O(n^k)
以上统计的的复杂度分析方式,大致可分为两位: 多项式量级和非多项式量级其中非多项式量级只有两个: O(2^n)和O(n!)
我们把时间复杂度为非多项式量级的算法问题叫做NP(Non-Deterministic Polynomial，非确定多项式)问题.
当数据规模N不断增加时,非多项式量级算法的执行时间会急剧增加,求解问题的执行时间会无限增长
所以,非多想时间复杂度的算法是非常低效的算法. 主要讲了几种,多项式时间复杂度
O(1)常量阶
O(1)只是常量级时间复杂度的一种表示方法,并不是指只执行了一行代码
如下: 只有3行代码,它的时间复杂度也是O(1),绝不是O(3)
代码分析案例5:
int i = 8; //1个unit_time
int j = 6;//1个unit_time
int sum = i + j;//1个unit_time
注意:
只要代码的执行时间不随着N的增大而增长,这样的代码的世界复杂度我们都认为是O(1);
即: 只要代码中不存在循环,递归,即使有N行代码,其时间复杂度也是O(1)
O(logn)对数阶和O(nlogn)线性对数阶
对数阶时间复杂度非常常见,同时也是最难肥西的一种时间复杂度
代码分析案例5:
i=1;//1个unit_time
while (i <= n) {
i = i * 2;//这里将是执行最多次的地方
}
显而易见,3行代码是循环次数最多的,所以我们只要计算出这里被执行了多少次,就知道整个代码的时间复杂度
遍历i的值从1开始取,每次循环就乘以2,当大于N时,循环结束.这就是高中我们学过的等比数列.遍历i的取值就是一个等比数列
这里我们列出来:
2^0 2^1 2^2 2^3 ... 2^k ... 2^x = n
所以, 我们只要知道了X的值是多少,就知道这行代码执行的次数.通过2^X=n求解X即可.
故X=log2(n),所以这段代码的时间复杂度就是O(log2(n))
代码分析案例6:
稍微改一下上面的代码
i=1;//1个unit_time
while (i <= n) {
i = i * 3;//这里将是执行最多次的地方
}
通过对比上面的案例,一眼就能看出来此处代码的时间复杂度为O(log3(n))
注意:
不管底数是2,3,4,10,我们都认为所有的对数阶的时间复杂度都是O(logn)
因为,对数之间是可以相互转换的,log3(n)就等于log3(2)*log2(n),
所以O(log3(n))=O(C*log2(n))其中`C=log3(2)是一个常量.
基于前面的理论: 在采用大O标记复杂度的时候,可以忽略系数,即O(Cf(n))=O(f(n))
所以O(log2(n))就等于O(log3(n)),因为在对数阶时间复杂度的表示防范里我们忽略对数的底数,统一表示未O(logn)
理解上面的O(logn)那么O(nlogn)就通了.
根据乘法法则, 如果一段代码的时间复杂度是O(logn),我们循环执行n遍,那么时间复杂度就是O(nlogn)了,
而且O(nlogn)也是一种常见的算法时间复杂度.
比如: 归并排序,快速排序的世时间复杂度都是O(nlogn)
O(m+n)和O(m*n)
整个和之前不一样的活, 这里的时间复杂度时由两个数据的规模来决定的.
代码案例7:
int cal(int m, int n) {
int sum_1 = 0;//1个unit_time
int i = 1;//1个unit_time
for (; i < m; ++i) {//n个unit_time
sum_1 = sum_1 + i;//n个unit_time
}
int sum_2 = 0;//1个unit_time
int j = 1;//1个unit_time
for (; j < n; ++j) {//n个unit_time
sum_2 = sum_2 + j;//n个unit_time
}
return sum_1 + sum_2;
}
可以看到,m和n是标识两个数据规模的, 我们无法事先评估m和n谁的量级大.
所以我们在表示复杂度时就不能简单的利用加法法则从而省略一个了.
所以上面代码的时间复杂度就是O(m+n).
针对这种情况原来的加法法则就不正确了, 我们要将加法法则改为: T1(m)+T2(n)=O(f(m)+g(n))
但是乘法法则依然有效: T1(n)*T2(n)=O(f(m)*f(n))
空间复杂度分析
理解了上面的大O复杂度表示法和时间复杂度分析,空间复杂度学起来会很简单
上面说了时间复杂度的全称是渐进时间复杂度, 表示算法的执行时间与数据规模之间的增长关系
同样, 空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系
代码案例8:
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
基本上分析起来和时间复杂度一样,可以看到第2行中,申请了一个空间存储遍历i,
但是他是常量阶的,跟数据规模n没有关系,所以直接忽略
第3行申请了一个大小为n的int类型数组,除此之外代码都没有占用更多的空间,所以整段代码的空间复杂度就是O(n)
常见的空间复杂度就是O(1),O(n),O(n^2),像是O(logn),O(nlogn)这样的对数阶复杂度平时都用不到
而且空间复杂度分析比时间复杂度分析要简单很多,所以对空间复杂度,刚我这几个就行.(老师说用不到...可是用不到你就不讲了吗?)
本章小结
谨记: 复杂度分析并不难，关键在于多练。
复杂度也叫做渐进复杂度,包括时间复杂度和空间复杂度,用来分析算法执行效率和数据规模之间的增长关系
可以粗略的表示越高阶复杂度的算法执行效率越低.常见的复杂度并不多,从低阶到高阶有: O(1),O(logn),O(n)O(nlogn),O(n^2)
几乎所有的数据结构和算法的复杂度都逃不出这几个:
个人总结
没啥总结的,比较简单.
复杂度分析-下
关键词
浅析最好、最坏、平均、均摊时间复杂度
- 最好时间复杂度 (best case time complexity)
- 最坏时间复杂度 (worst case time complexity)
- 平均时间复杂度 (average case time complexity)
- 均摊时间复杂度 (amortized time complexity)
最好和最坏时间复杂度
- 最好时间复杂度,就是在理想状态下,这段代码的时间复杂度
- 最坏时间复杂度,就是在最坏状态下,这段代码的时间复杂度
代码案例2-1
// n表示数组array的长度,个人认为时间复杂度是O(n)
int find(int[] array, int n, int x) {
int i = 0; //1个unit_time
int pos = -1; //1个unit_time
for (; i < n; ++i) { //n个unit_time
if (array[i] == x) pos = i; //n个unit_time
}
return pos;
}
这段代码的主要功能就是在一个数组中,查找变量x出现的位置,如果没有找到则返回-1,时间复杂度为O(n),这里的n代表数组长度.
在数组中查找一个数据,并不需要每次都把整个数组都遍历一遍,因为有可能中途就找到了想要的数据就可以退出循环返回属于了;
而上面的代码及时找到了也还会继续遍历因为没有退出循环.所以代码不够高效下面我们优化一下.
代码案例2-2
// n表示数组array的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
这时候这段代码的世间法复杂度显然已经不再是单纯的O(n)就能解释通了的.
因为说,要查找的遍历x可能处于数组的任何位置,如果在第一位,那么就不需要再继续执行下面的n-1个数据了,此时的复杂度为O(1)
但是如果数组中不存在变量x,那我们就要把整个数组全部遍历一遍,此时的复杂度就变成了O(n)
故:不同情况下,此段代码的时间复杂度时不一样的
此时就引入了本章开始时记录的三个概念: 最好时间复杂度,最坏时间复杂度,平均时间复杂度
-
此段代码最好时间复杂度就是O(1)
-
此段代码最坏时间复杂度就是O(n)
-
此段代码平均时间复杂度我们下面接着说,因为比较复杂,所以单独拎出来说.
平均情况时间复杂度
最好时间复杂度和最坏时间复杂度都是在对应在极端情况下的时间复杂度,我们需要一个通常情况下的复杂度分析.
此时就引入了上面所说的平均时间复杂度
接着以代码案例2-2来分析:
要查找遍历x的位置,有n+1种情况: 在数组的0-n-1位置中和不再数组中
这里把每种情况下,需要遍历的元素个数累加起来,然后再除以n+1就可以得到需要遍历的元素个数的平均值,如下图:
1+2+3+...+n+n/n+1=n(n+3)/2(n+1)
之前我们说了,时间复杂度的大O标记法中,可以省略:系数,低阶,常量,所以我们把上面的公式优化之后得到的平均世间法复杂度就是O(n)
但是这个结论虽然正确,但是有点小问题,因为这里的n+1种情况出现的概率并不是一样的
要知道,要查找变量x,要么在数组中,要么不再.这里两种情况对应的概率统计起来都很麻烦,这里我们结社在与不在给为1/2
另外要查找的数据出现在0~n-1这n个位置的概率也是一样的,为1/n.
所以,根据概率乘法则,要查找的数据出现在0~n-1中任意位置的概率就是1/(2n)
1*1/2n+2*1/2n+3*1/2n+...+n*1/2n+n*1/2n=3n+1/4
这个值就是概率论中的加权平均值,也叫期望值. 所以平均时间复杂度的全称应该叫做,加权平均时间复杂度或者期望时间复杂度
在引入概率之后,这段代码的加权平均值为(3n+1)/4, 用大O表示法来表示,去掉系数和常量,这段代码的加权平均时间复杂度依然是O(n)
如果觉得平均时间复杂度分析很复杂那就对了,还要设计概率论的知识.
但是没关系,因为大多数情况下,我们并不需要区分最好,最坏,平均情况的时间复杂度三种情况,平均复杂度只在特殊情况下才会用到.
只有同一段代码在不同情况下,时间复杂度有量级的差距,我们才会使用者三种复杂度表示法来区分.
均摊时间复杂度
这里整个更攒劲的概念,均摊时间复杂度,以及它所对应的分析方法**,摊还分析(或者叫平摊分析).**
均摊时间复杂度和平均时间复杂度有点像,但却不同.且均摊时间复杂度的应用场景比平均复杂度更加特殊和有限.
代码案例2-3:
// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {//如果数组存满
int sum = 0;//存储求和结果
for (int i = 0; i < array.length; ++i) {//遍历数组
sum = sum + array[i];//逐个求和
}
array[0] = sum;//将和放入数组的第一个元素
count = 1;//将变量count置为1,下次填充数据的时候,数据的下标就会为1,因为0已经被我们的求和变量sum占用了
}
//数组未存满,直接将传入的val变量存入到数组中,下标直接用变量count,因为count初始值为0,且自增
array[count] = val;
++count;//添加一个元素之后,让count自增,以便于下次填充数据时作为下标使用
}
这段代码实现了一个往数组汇总插入数据的功能当数组满了之后,也就是代码中count==array.lenth 时,
我们用for循环来遍历数组求和并清空数组,将求和之后的sum只放到数组的第一个位置,然后再将新的数据插入.
但是如果数组一开始就有空闲空间,则直接将数据插入数组.
分析复杂度:
理想状态下, 数组有空闲位置,直接插入数据到下标为count的位置,所以最好时间复杂度为O(1)
最坏状态下,数组没有空闲位置,此时需要先将数组遍历一遍求和,然后再将数据插入,所以最坏时间复杂度为O(n)
而平均时间复杂度时O(1),依然通过上面说的概率论的方法来分析
假设数组长度为n,根据数据插入位置的不同,可以分为n种情况,每种情况的世界复杂度时O(1).
除此之外,有一种额外的情况,就是数组没有空闲时间时插入一个数据,此时时间复杂度为O(n).
而且这种n+1种情况发生的概率一样,都是1/(n+1)
所以,根据加权平均的计算方法,我们求得的平均时间复杂度就是:
(1*1/n+1)+(1*1/n+1)+...+(1*1/n+1)+(n*1/n+1)=O(1)
到此为止, 最好,最坏,平均,时间复杂度都已经理解了.
但是上面代码2-2例子中的平均复杂度分析其实不需要那么复杂,至少可以不用概率论的知识.
来对比一下代码2-3的insert()函数和2-2的find()函数,就发现两者有很大的差距
第一个区别:
首先find()在极端情况下,复杂度才为O(1),但是insert()在大部分情况下,时间复杂度都是O(1)
只有特别情况下,复杂度才比较高,为O(n).
第二个区别:
对于insert()来说O(1)时间复杂度的插入和O(n)时间复杂度的插入,出现的非常有规律且有一定的前后时序关系
通常都是一个O(n)插入之后,紧跟着n-1个O(1)的插入操作,循环往复
所以说,针对这一种特殊常见的复杂度分析,并不需要像之前做平均复杂度分析,要找出所有的输入情况和相应的发生概率
然后再计算加权平均值.
像这样的特殊情况,引入了一种更加简单的分析方法: 摊还分析法, 通过摊还分析得到的世界复杂度命名为,均摊时间复杂度.
均摊时间复杂度分析
还用代码案例2-3的iinsert()来做分析,每一次O(n)的插入操作,都会跟着n-1次O(1)的插入操作.
所以把耗时多的那次操作均摊到接下来的n-1次耗时少的操作上,均摊下来,这一组连续操作的均摊时间复杂度就是O(1)
均摊时间复杂度和摊还分析应用场景比较特殊,并不会经常用到.为了理解,这里简单总结一下应用场景,知道咋回事就行:
# 以下内容复制自课程,读了一遍感觉没啥用,就不记了.
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。
内容小结
上面学习了: 最好时间复杂度,最坏时间复杂度,平均时间复杂度,均摊时间复杂度.
之所以学习这些是因为同一段代码,在不同情况下,复杂度的量级可能会不一样
了解了这些概念之后,可以同价全面的展示一段代码的执行效率.
平均和均摊搞不懂没事,平时不会用,且后面数据结构和算法学习过程中,会不断的实践.
课后题
整一波课后题
代码案例2-4:
// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个2倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来array数组中的数据依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array复制给array，array现在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 将element放到下标为i的位置，下标i加一
array[i] = element;
++i;
}
分析上面代码的时间复杂度
上面add()函数的大致逻辑是,传一个值element进来,如果数组array空间足够则直接将element插入到数组中下标为i的位置
同时让i自增,一边下次插入数据时使用
如果数组不够则以array*2的大小重新申请一个内存,即数组new_array,并逐个遍历数组array,将array中的元素逐个放入到new_array中
再用新的数组new_array覆盖原来的数组array
这个流程几乎和代码案例2-3的insert()函数差不多,需要关注的地方,也就是:
- 如果数组array有空缺,则直接插入数据,此时时间复杂度为O(1)
- 如果数组满员,则进入一个简单for循环进行处理,此时时间复杂度为O(n)
所以三个时间复杂度分别是:
-
最佳时间复杂度: O(1)
-
最差时间复杂度: O(n)
-
平均时间复杂度://todo 不知道
个人总结
概率学不好搞.看完这个,快去补充一下概率学,再复习一下高中代数.
