算法是解决问题的一种方法。例如高斯的高斯公式，计算面积的公式等。都是一种算法，用来解决某些问题。
算法特性
- 有穷行: 算法可以在某一个条件下自动结束而不是出现无限循环
- 确定性: 算法执行的每一步骤在一定条件下只有一条执行路径，一个相同的输入对应相同的一个输出
- 可行性: 算法每一步骤都必须可行，能够通过有限的执行次数完成
- 输入: 算法具有零个或多个输入
- 输出: 算法至少有一个或多个输出
算法效率衡量方法
- 正确性
只有一个能解决问题的正确算法才是我们所需要的。所以设计好一个算法的首要目标就是这个算法能解决问题。 - 可读性
代码是写给计算机运行的，而读代码是我们程序员来读的，一个算法如果写的晦涩难懂难以理解，这对未来的维护以及拓展将会造成很大的问题。所以并不是代码越少就是越厉害，有易懂的注释与清晰的逻辑才是最美的。 - 健壮性
一个好的算法需要考虑到各种情况，对各种情况都要进行处理，避免某些情况造成算法的错误计算等。 - 时间效率和存储效率
这就是我们经常听到的时间复杂度与空间复杂度，花最少的消耗与最少的消耗完成任务。
时间复杂度(大O表示法)
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。
推导大O阶方法
- 用常数1取代运行时间中所有常数 3->1 O(1)
- 在修改运行次数函数中,只保留最高阶项 n³+2n²+5 -> O(n³)
- 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n³ -> n³
常见的算法复杂度
-
常数阶-O(1)
//1常数阶 执行3次。O(1)
void testNum1(int n){
int sum = 0 ;//执行一次
sum = (n+1)*n/2; //执行一次
printf("sum=%d\n",sum);//执行一次
}
-
线性阶-O(n)
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
-
平方阶-O(n²)
//x=x+1; 执行n*n次 ->O(n²)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}
-
对数阶-O(logn)
/* 2的x次方等于n x = log2n ->O(logn)*/
void testA(int n){
int count = 1; //执行1次
//n = 10
while (count < n) {
count = count * 2;
}
}
-
立方阶-O(n³)
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}
-
nlogn阶-O(nlogn)
void testA(int n){
int count = 1; //执行1次
//n = 10
for (int i = 0; i< n; i++) {
while (count < n) {
count = count * 2;
}
}
}
-
指数阶（不考虑）
image.png
0(1) < 0(logn) < 0(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
最坏情况与平均情况
我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置，那么时间复杂度为O(n)。
平均运行时间是期望的运行时间。
最坏运行时间是一种保证。在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
空间复杂度
空间复杂度就是运行某一个算法，需要多少额外的辅助空间来进行这个算法的运行。
算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
如果算法执行时所需要的辅助空间相对于输入数据量是一个常数,则成这个算法原地工作,辅助空间为O(1).
int temp = a;
a = b;
b = temp;
消耗了额外的一个变量，即空间复杂度为O(1)
int a[n] = {0};//n为常数
for(int i = 0; i < n;i++){
a[i] = array[n-i-1];
}
for(int i = 0; i < n; i++){
array[i] = a[i];
}
消耗了额外的n个空间的数组，即空间复杂度为O(n)
常用算法
| 排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不一顶 | O(n) |
| 插入排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
网友评论