常见算法
# 冒泡排序原理和实现
# 算法的概念
解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作 一个问题有多种算法，每种算法有不同的效率。
一个算法有五个特征：
- 有穷性：算法可以计算完，不能无穷尽的计算下去
- 确切性：每一步都是有意义的
- 输入项：可以输入
- 输出项：给一个结果
- 可行性：可以执行
# 时间复杂度和空间复杂度的概念
算法分析的目的在于选择合适的算法和改进算法，一个算法的评价主要在于时间复杂度和空间复杂度
# 时间复杂度
执行算法所需要的计算工作量，一般来说计算算法是问题规模n的函数f(n),算法的时间复杂度也因此记做T(n)=O(f(n))
问题规模n越大，算法执行的时间的增长率与f(n)的增长率正相关，称做渐进时间复杂度(Asymptotic Time Complexity)
时间复杂度的计算方式 ：O(n^2)、O(1)、O(n)
比如：从1到n进行累加，计算了n次，则时间复杂度为O(n)
# 1+2+3+4....+n
$sum = 0;
for($i=1;$i<=$n;$i++) {
$sum+=$i;
}
1
2
3
4
5
2
3
4
5
用常数1来取代所有时间中的加法常数，对于计算次数固定的不论次数是多少，则使用O(1)来进行表示
# 1+2+3+4....+n
$sum = 0;
for($i=1;$i<=3;$i++) {
$sum+=$i;
}
1
2
3
4
5
2
3
4
5
在修改后的运行函数中，只保留最高阶项，对于计算次数如果为n^2+n+1，则使用最高阶来表示O(n^2)
# 1+2+3+4....+n
$sum = 0;
// 里层循环n次，外层循环n次，计做n^2
for($i=1;$i<=$n;$i++) {
// 计算n次
for($j=$i;$j<=$n;$j++) {
$sum+=$i;
}
}
// n
for($i=1;$i<=$n;$i++) {
// 计算n次
$sum+=1;
}
// 1
echo $n;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
如果最高阶存在且不是1，则去除以与这个项相乘的常数。对于计算次数为2n^2+3n+1,则时间复杂度为O(n^2)
# 1+2+3+4....+n
$sum = 0;
//
for($i=1;$i<=$n;$i++) {
$sum+=$i;
}
1
2
3
4
5
6
2
3
4
5
6
常见的时间复杂度
- 常数阶 O(1)
- 线性阶O(n)
- 平(立)方阶O(n^2)/O(n^3)
- 特殊平方阶：O(n^2/2+n/2)计做O(n^2)
- 对数阶：O(log2n)
- 指数阶
效率：值越小，代表效率越高,如下是各个算法的效率排行
O(1) > O(log2n) > O(n) > O(nlog2n) > O(n^2) > O(n>3) > O(2^n) > O(n!) > O(n^n)
最坏情况：最坏情况时的运行时间，一种保证，如果没有特别说明，说的时间复杂度即为最坏情况的时间复杂度 平均情况：期望的运行时间
# 空间复杂度
算法需要消耗的内存空间 ，记作S(n)=O(f(n))。包括程序代码所占用的空间，输入数据所占用的内存空间和辅助变量所占用的内存空间。计算和表达方式与时间复杂度类似，一般用复杂度的渐进性来表示。 有时用空间换时间
# 常见的排序算法
# 常见的查找算法
上次更新: 2020/12/31, 06:55:18