算法
算法
算法
是指令的集合，是为了解决特定问题而规定的一系列操作
一个算法通常来说具有以下五个特性：
1.输入：一个算法应以待解决的问题的信息作为输入
2.输出：输入对应指令集处理后得到的信息
3.可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成
4.又穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成的，因此整个算法也是在有限时间内可以结束的
5.确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指定集结果总是相同的
简单的说，算法就是计算机解题的过程
评价算法优劣的依据：复杂度（时间复杂度和空间复杂度）
算法时间复杂度（Time Complexity）
时间拼读
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道
一个算法话费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，话费的时间就多
算法中的语句执行次数成为语句频度或时间频度，表示为T（n），n表示问题的规模
时间复杂度
我们想知道问题的规模，而不是具体的次数，此时引入时间复杂度
T（n）=O（f（n））
或者说：时间复杂度及时时间频度去掉低价项和首项常数
最坏时间复杂度和平均时间复杂度
最坏情况下的时间复杂度称为最坏时间复杂度。一般不特别说明，讨论时间复杂度均是最坏时间复杂度
这样做的原因：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长
平均复杂度：难计算、很多情况下平均时间复杂度和最坏时间复杂度是一样的
所以一般讨论最坏时间复杂度
O：时间复杂度的上界（最坏情况<=），T（n）=O（n2）
Ω：时间复杂度的下界（最好情况>=），T（n）=Ω（n2）
Θ：时间复杂度的精确阶（最好和最坏是同一个阶=），T（n）=Θ（n2）
时间复杂度计算
1.找出算法中的基本语句：
```plain text 算法中执行次数最多的语句就是基本语句，通常是最内层循环的循环体
1
2
3
4
5
2.计算基本语句的执行次数的数量级
```plain text
只需计算基本语句执行次数的数量级
3.用O表示算法的时间性能
时间复杂度举例
一个简短语句的时间复杂度O（1）
int count=0;
T(n)=O(1)
100个简单语句的时间复杂度也是O(1).(100是常数，不是趋向无穷大的n)
一个循环的时间复杂度为O(n)
int n=8,count=0;
for(int t=i;i<=n;i++){
```plain text count++;
1
2
3
4
5
6
7
8
9
10
11
}
T(n)=O(n)
时间复杂度为O(log2 n)的循环语句
for(int i=1;i<=n;i*=2){
```plain text
count++;
}
时间复杂度为O(n2)二重循环
int n=8,count=0;
for(int i=1;i<=n;i++){
```plain text for(int j=1;j<=n;j++){
1
count++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
}
时间复杂度为O(nlog2 n)的二重循环
for(int i=1;i<=n;i*=2){
```plain text
for(int j=1;j<=n;j++){
count++;
}
}
时间复杂度为O(n2)的二重循环
for(int i=1;i<=n;i++){
```plain text for(int j=1;j<=i;j++){
1
count++;
} ```
}
常用的时间复杂度级别
常数阶O(1)
对数阶O(log2 n)
线性阶O(n)
线性对数阶O(nlog2 n)
平方阶O(n2)
立方阶O(n3)
…
k次方阶(nk)
指数阶O(2n)
阶乘阶O(n!)
执行效率越来越低
算法空间复杂度
算法的存储量包括：
1.程序本身所占用空间
2.输入数据所占空间
3.辅助变量所占空间
输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间
空间复杂度是对一个算法在运行过程中临时占用的 存储空间大小的亮度
使用递归算法，每次调用本身都要分配空间，占用空间多，效率低下
注意：
1.空间复杂度相比时间复杂度分析要少
2.对于算法来说，代码一般都比较简短，短发本身所占用的存储空间较少，但运行时需要占用较多的临时工作单元；
若写成非递归算法，代码一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元