1.算法的复杂度
算法在编写成可执行程序后,运行需要耗费时间和空间资源 因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的 即算法的时间复杂度和空间复杂度
时间复杂度主要衡量一个算法的快慢,而空间复杂度主要衡量一个算法运行所需的额外空间
在计算机发展的早期,计算机的存储容量很小,所以对空间的复杂度是很在乎,但是经过计算机行业的迅速发展,
计算机的存储容量已过达到了很高的程度,所以我们如今已经不再特别需要关注一个算法的空间复杂度了
2 大 O 的渐进表示法
大 O 符号（Big O notation）是用于描述函数渐进行为的数学符号 推导大 O 阶的方法
1.用常数 1 取代运行时间中的所以加法常数
2.在修改后的运行次数函数中，只保留最高阶的项
3.如果最高阶的项存在且不是 1，则除去与这个项目相乘的常数，得到的结果就是大 O 阶
3.时间复杂度概念
时间复杂度的定义: 在计算机科学当中,算法的时间复杂度,是一个函数,
它是定量描述了该算法的运行时间.一个算法执行所耗费的时间
从理论上来说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道, 但是我们并不需要这么做
所以我们就有了时间复杂度的分析方式:
一个算法所花费的时间与其中语句执行的次数成正比,算法中的基本操作的次数,为算法的时间复杂度
即找到某条语句与问题规模 N 之间的数学表达式，就是算出了该算法的复杂度
所以计算算法的时间复杂度,就是计算算法中的基本操作的执行次数
3.1 时间复杂度分析案例
- 例题 1:
求得 Func1 的事件复杂度，F(n)=N*N+2*N+10
随着 N 的增大，常数 10 对 F(n)的影响较小
所以这道题的时间复杂度为 O(N^2)
- 例题 2:
F(n)=2N+10
随着 N 的增大，常数 10 对 F(n)的影响较小
当 N 无限大的时候 N 和 2N 是同一个级别
最高阶为 2，则除去与这个项目相乘的常数 2
所以时间复杂度为 O(N)
- 例题 3:
这道题 M 和 N 都是 O(n)级别的
一般情况下，时间复杂度计算时未知数用的都是 N，但是也可以是其他字符
如果没有给定条件，那么这道题的复杂度是 O(M+N)
如果给定条件 M 远大于 N，则为 O(M)
如果 N 远大于 M，则为 O(N)
如果差不多大，可以为 O(M) 也可以为 O(N)
- 例题 4:
可以看出 ++count 执行了 100 次，也就是常数次
所以时间复杂度为 O(n)
- 例题 5:
冒泡排序的时间复杂度的分析，根据其思想，每次内部循环完成，都会把排好的数字放到最后
所以循环完毕后，可以看出，冒泡排序执行的数是一个等差数列求和即((N-1)+1)=*(N-1)/2=N*(N-1)/2
所以时间复杂度为 O(N^2)
- 例题 6:
二分查找，每次都会从当前数组的一半开始找，相当于每次都除以 2
最好的情况是 O(1)
最坏的情况也就是找不到或者最边上，也就是 2^x=N,即求 N 的对数
对于一个算法，我们基本上看他的最坏情况
所以二分查找的时间复杂度为 O(log2n)
- 例题 7:
斐波那契数列递归写法,是一个运行效率特别慢的写法
以 Fib(8) 为例
第一层节点个数为 2^0,第二层为 2^1,第三次 2^2 以此类推直到 2^(n-1),项数为 n，还有一侧节点是不满的，不满的节点数记录为 x
所以求斐波那契数列的操作数，F(n)=2^n-1+x
所以时间复杂度为 O(2^n)
4.算法的空间复杂度
空间复杂度是一个数学表达式,是对一个算法在运行过程中临时占用的存储空间大小的度量
空间复杂度不是程序占用了多少字节的空间,因为这个没大意义,所以空间复杂度算得是变量的个数
空间复杂度计算规则基本跟时间复杂度类似,也使用大 O 渐进表示法
函数运行所需的栈空间(存储参数,局部变量,寄存器信息)在编译期间已经确定好了,
因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定
4.1 算法的时间复杂度分析案例
- 例题 1:
根据冒泡排序的思想, 总共有两个变量在循环当中
循环内部变量 j 每次循环完后会释放,然后再次创建
所以,总共就 2 个变量,空间复杂度为 O(1)
- 例题 2:
由于是计算斐波那契数列前 N 项的数组
所以每次,都会在数组后面增加一个元素,占用一个空间
所以空间复杂度就是 O(N)
- 例题 3:
递归过程中,每个栈帧的创建都会消耗一定的空间
所以计算阶乘的空间复杂度,就是计算递归深度
所以空间复杂度为 O(N)
- 例题 4:
在计算斐波那契数列递归的空间复杂度,的时候
要注意,空间是可以重复利用,不累计的,时间是一去不复返,累计的
所以空间复杂度,不是 O(2^n), 因为每次递归完最深处后,内存空间会被回收
所以,其空间复杂度就是递归的深度 O(N)
...