✨✨ 欢送大家来到贝蒂大讲堂✨✨养成好习惯，先赞后看哦~
所属专栏：数据结构与算法
贝蒂的主页：Betty‘s blog
前言
随着应用程序变得越来越简单和数据越来越丰盛，几百万、几十亿甚至几百亿的数据就会呈现，而对这么大对数据进行搜寻、插入或者排序等的操作就越来越慢，人们为了解决这些问题，进步对数据的管理效率，提出了一门学科即：数据结构与算法
1. 什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的形式，指相互之间存在一种或多种特定关系的数据元素的汇合。
下标是常见的数据结构:
| 名称 | 定义 |
|---|---|
| 数组（Array） | 数组是一种聚合数据类型，它是将具备雷同类型的若干变量有序地组织在一起的汇合。 |
| 链表（Linked List） | 链表是一种数据元素依照链式存储构造进行存储的数据结构，这种存储构造具备在物理上存在非间断的特点。 |
| 栈（Stack） | 栈是一种非凡的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作 |
| 队列（Queue） | 队列和栈相似，也是一种非凡的线性表。和栈不同的是，队列只容许在表的一端进行插入操作，而在另一端进行删除操作。 |
| 树（Tree） | 树是典型的非线性构造，它是包含，2 个结点的有穷汇合 K |
| 堆（Heap） | 堆是一种非凡的树形数据结构，个别探讨的堆都是二叉堆。 |
| 图（Graph） | 图是另一种非线性数据结构。在图构造中，数据结点个别称为顶点，而边是顶点的有序偶对 |
2. 什么是算法
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输出，并产生出一个或一组值作为输入。简略来说算法就是一系列的计算步骤，用来将输出数据转化成输入后果。
算法个别分为：排序，递归与分治，回溯，DP，贪婪，搜索算法
- 算法往往数学密切相关，就如数学题一样，每道数学题都有不同的解法，算法也是同理。
3. 复杂度剖析
3.1 算法评估
咱们在进行算法剖析时，经常须要实现两个指标。一个是找出问题的解决办法，另一个就是找到问题的最优解。而为了找出最优解，咱们就须要从两个维度剖析：
- 工夫效率：算法运行的快慢
- 空间效率：算法所占空间的大小
3.2 评估办法
评估工夫的办法次要分为两种，一种是试验分析法，一种是实践分析法。
(1) 试验分析法
试验分析法简略来说就是将不同种算法输出同一台电脑，统计工夫的快慢。然而这种办法有两大缺点：
- 无奈排查试验本身条件与环境的条件的影响：比方同一种算法在不同配置的电脑上的运算速度可能齐全不同，甚至后果齐全相同。咱们很难排查所有状况。
- 老本太高：同一种算法可能在数据少时体现不显著，在数据多时速率较快
(2) 实践分析法
因为试验分析法的局限性，就有人提出了一种实践测评的办法，就是渐近复杂度剖析(asymptotic complexity analysis)，简称复杂度剖析。
这种办法体现算法运行所需的工夫（空间）资源与输出数据大小之间的关系，能无效的反馈算法的优劣。
4. 工夫复杂度与空间复杂度
4.1 工夫复杂度
一个算法所破费的工夫与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的工夫复杂度。
为了精确的表述一段代表所需工夫，咱们先假如赋值(=)与加号(+)所需工夫为1ns，乘号(×)所需工夫为2ns，打印所需为3ns。
让咱们计算如下代码所需总工夫：
int main(){ int i = 1;//1ns int n = 0;//1ns scanf("%d", &n); for (i = 0; i < n; i++) { printf("%d ", i);//3ns } return 0;}计算工夫如下：
$$T(n)=1+1+3×n=3n+2$$
然而实际上统计每一项所需工夫是不事实的，并且因为是实践剖析，当n—>∞时，其余项皆可疏忽，T(n)的数量级由最高阶决定。所以咱们计算工夫复杂度时，能够简化为两个步骤：
- 疏忽除最高阶以外的所有项。
- 疏忽所有系数。
而上述代码工夫能够记为O(n)，这种办法被称为大O的渐进表示法。如果计算机后果全是常数，则记为O(1)。
- 并且计算复杂度时，有时候会呈现不同状况的后果，这是应该以最坏的后果思考。
4.2 空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中长期占用存储空间大小的量度 。空间复杂度的示意也遵循大O的渐进表示法
让咱们计算一下冒泡排序的空间复杂度
// 计算BubbleSort的空间复杂度？void BubbleSort(int* a, int n){ assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break; }}- 通过观察咱们能够看出，冒泡排序并没有开拓多余的空间，所以空间复杂度为O(1).
5. 复杂度分类
算法的复杂度有几个量级，示意如下：
$$O(1) < O( log N) < O(N) < O(Nlog N) < O(N 2 ) < O(2^ ) < (O!)$$
- 从左到右复杂度顺次递增，算法的毛病也就越显著
图示如下：
5.1 常数O(1)阶
常数阶是一种十分疾速的算法，然而在理论利用中十分难实现
以下是一种工夫复杂度与空间复杂度皆为O(1)的算法：
int main(){ int a = 0; int b = 1; int c = a + b; printf("两数之和为%d\n", c); return 9;}5.2 对数阶O(logN)
对数阶是一种比拟快的算法，它个别每次缩小一半的数据。咱们罕用的二分查找算法的工夫复杂度就为O(logN)
二分查找如下：
int binary_search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是须要查找的值{ int left = 0; int right = size - 1; // 定义了target在左闭右闭的区间内，[left, right] while (left <= right) { //当left == right时，区间[left, right]依然无效 int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，避免溢出 if (nums[middle] > target) { right = middle - 1; //target在左区间，所以[left, middle - 1] } else if (nums[middle] < target) { left = middle + 1; //target在右区间，所以[middle + 1, right] } else { //既不在右边，也不在左边，那就是找到答案了 return middle; } } //没有找到目标值 return -1;}空间复杂度为O(logN)的算法，个别为分治算法
比方用递归实现二分算法：
int binary_search(int ar[], int low, int high, int key){ if(low > high)//查找不到 return -1; int mid = (low+high)/2; if(key == ar[mid])//查找到 return mid; else if(key < ar[mid]) return Search(ar,low,mid-1,key); else return Search(ar,mid+1,high,key);}每一次执行递归都会对应开拓一个空间，也被称为栈帧。
5.3 线性阶O(N)
线性阶算法，工夫复杂度与空间复杂度随着数量平均变动。
遍历数组或者链表是常见的线性阶算法，以下为工夫复杂度为O(N)的算法：
int main(){ int n = 0; int count = 0; scanf("%d", &n); for (int i = 0; i < n; i++) { count += i;//计算0~9的和 } return 0;}以下为空间复杂度为O(N)的算法
int main(){ int n = 0; int count = 0; scanf("%d", &n); int* p = (int*)malloc(sizeof(int) * n); //开拓大小为n的空间 if (p == NULL) { perror("malloc fail"); return -1; } free(p); p=NULL; return 0;}5.4 线性对数阶O(NlogN)
无论是工夫复杂度还是空间复杂度，线性对数阶个别呈现在嵌套循环中，即一层的复杂度为O(N)，另一层为O(logN)
比如说循环应用二分查找打印：
int binary_search(int nums[], int size, int target) //nums是数组，size是数组的大小，target是须要查找的值{ int left = 0; int right = size - 1; // 定义了target在左闭右闭的区间内，[left, right] while (left <= right) { //当left == right时，区间[left, right]依然无效 int middle = left + ((right - left) / 2);//等同于 (left + right) / 2，避免溢出 if (nums[middle] > target) { right = middle - 1; //target在左区间，所以[left, middle - 1] } else if (nums[middle] < target) { left = middle + 1; //target在右区间，所以[middle + 1, right] } else { //既不在右边，也不在左边，那就是找到答案了 printf("%d ", nums[middle]); } } //没有找到目标值 return -1;}void func(int nums[], int size, int target){ for (int i = 0; i < size; i++) { binary_search(nums, size, target); }}空间复杂度为O(NlogN)的算法，最常见的莫非归并排序
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){ int i = startIndex, j=midIndex+1, k = startIndex; while(i!=midIndex+1 && j!=endIndex+1) { if(sourceArr[i] > sourceArr[j]) tempArr[k++] = sourceArr[j++]; else tempArr[k++] = sourceArr[i++]; } while(i != midIndex+1) tempArr[k++] = sourceArr[i++]; while(j != endIndex+1) tempArr[k++] = sourceArr[j++]; for(i=startIndex; i<=endIndex; i++) sourceArr[i] = tempArr[i];} //外部应用递归void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) { int midIndex; if(startIndex < endIndex) { midIndex = startIndex + (endIndex-startIndex) / 2;//防止溢出int MergeSort(sourceArr, tempArr, startIndex, midIndex); MergeSort(sourceArr, tempArr, midIndex+1, endIndex); Merge(sourceArr, tempArr, startIndex, midIndex, endIndex); }}5.5 平方阶O(N^2^)
平方阶与线性对数阶类似，常见于嵌套循环中，每层循环的复杂度为O(N)
工夫复杂度为O(N^2^)，最常见的就是冒泡排序
void BubbleSort(int* a, int n){ assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i - 1] > a[i]) { Swap(&a[i - 1], &a[i]); exchange = 1; } } if (exchange == 0) break; }}计算过程如下;
$$T(N)=1+2+3+......+n-1=(n^2-n)/2=O(n^2)$$
空间复杂度为O(N^2^)，最简略的就是动静开拓。
{ int n = 0; int count = 0; scanf("%d", &n); int* p = (int*)malloc(sizeof(int) * n*n); //开拓大小为n的空间 if (p == NULL) { perror("malloc fail"); return -1; } free(p); p=NULL; return 0;}5.6 指数阶O(2^N^)
指数阶的算法效率低，并不罕用。
常见的工夫复杂度为O(2^N^)的算法就是递归实现斐波拉契数列：
int Fib1(int n){ if (n == 1 || n == 2) { return 1; } else { return Fib1(n - 1) + Fib1(n - 2); }}粗略预计
$$T(n)=2^0+2^1+2^2+.....+2^(n-1)=2^n-1=O(2^N)$$
- 值得一提的是斐波拉契的空间复杂度为O(N)，因为在递归至最深处后往回归的过程中，后续空间都在销毁的空间上建设的，这样能大大提高空间的利用率。
空间复杂度为O(2^N^)的算法个别与树无关，比方建设满二叉树
TreeNode* buildTree(int n) { if (n == 0) return NULL; TreeNode* root = newTreeNode(0); root->left = buildTree(n - 1); root->right = buildTree(n - 1); return root;}5.7 阶乘阶O(N!)
阶乘阶的算法复杂度最高，简直不会采纳该类型的算法。
这是一个工夫复杂度为阶乘阶O(N!)的算法
int func(int n){ if (n == 0) return 1; int count = 0; for (int i = 0; i < n; i++) { count += func(n - 1); } return count;}示意图：
- 空间复杂度为阶乘阶O(N!)的算法并不常见，这里就不在一一列举。