前言
随着应用程序变得越来越复杂和数据越来越丰富，几百万、几十亿甚至几百亿的数据就会出现，而对这么大对数据进行搜索、插入或者排序等的操作就越来越慢，人们为了解决这些问题，提高对数据的管理效率，提出了一门学科即：数据结构与算法
1. 什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合，它涉及到如何组织和存储数据，以便在程序中进行高效的访问和操作。
数据结构的基本类型：
数据结构类型
| 名称 | 定义 |
| 数组（Array） | 一组连续的内存空间，用来存储相同类型的数据。 |
| 链表（Linked List） | 由一系列节点组成，每个节点包含数据和指向下一个节点的指针。 |
| 栈（Stack） | 一种后进先出的数据结构。 |
| 队列（Queue） | 一种先进先出的数据结构。 |
| 树（Tree） | 由节点和边组成的层级结构。每个节点可以有任意数量的子节点。树的最顶层节点称为根节点，没有子节点的节点称为叶子节点。 |
| 堆（Heap） | 一种完全二叉树的结构。每个节点的值都小于等于（或大于等于）其子节点的值。 |
| 图（Graph） | 由节点和边组成的非线性结构。节点之间可以有多条边相连。可以用来表示网络、地图等复杂结构。 |
| 哈希表(Hash Table) | 一种通过哈希函数将关键字映射到表中位置的数据结构。 |
不同的数据结构适用于不同的场景，选择合适的数据结构可以提高程序的效率。
2. 什么是算法
算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
常见的算法有：
- 排序算法(Sorting Algorithm):将一组数据按照一定规则进行排序，如冒泡排序、选择排序、插入排序、快速排序等。
- 查找算法(Search Algorithm):在一个有序的数据集中查找指定的数据，如二分查找、线性查找等。
- 递归算法(Recursion Algorithm):通过函数自身的调用实现对问题的解决，如斐波那契数列、阶乘等。
- 动态规划算法(Dynamic Programming Algorithm):通过将问题分解成更小的子问题来解决复杂问题，如背包问题、最长公共子序列等。
- 贪心算法(Greedy Algorithm):每次选择局部最优解来解决问题，如最小生成树算法、最短路径算法等。
3. 数据结构和算法的重要性
- 高效解决问题：数据结构和算法可以帮助我们更有效地解决各种问题，包括排序、搜索、图形遍历等。通过使用合适的数据结构和算法，我们可以大大提高计算效率，节省时间和空间资源。
- 可扩展性：随着计算机硬件和软件的发展，我们需要处理的问题变得越来越复杂。数据结构和算法提供了一种可扩展的方法来应对这些挑战，使得我们能够更好地适应不断变化的需求。
- 优化程序性能：对于需要大量计算的应用程序，优化程序性能至关重要。数据结构和算法可以帮助我们减少不必要的计算，提高程序运行速度，从而提高用户体验。
- 提高代码质量：使用适当的数据结构和算法可以确保我们的代码更加简洁、易于理解和维护。这有助于提高代码质量，降低出错概率，并为团队协作创造更好的环境。
- 适用于各种领域：数据结构和算法不仅在计算机科学领域具有重要意义，而且在其他领域也发挥着关键作用。例如，在金融、医疗、物流等领域，高效的数据处理方法同样具有重要价值。
一、算法效率的衡量
那么提到算法效率，我们肯定想知道如何衡量一个算法的好坏？
例如以下代码：
long long Fib(int N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。如果你不知道什么是复杂度时，你可能就无法正确的完成题目。因此，我们在学习数据结构与算法的第一步，就是要理解什么是复杂度。
- 时间复杂度主要衡量的是一个算法的运行速度。由于在不同的硬件上，程序运行的速度会有所不同，所以时间复杂度代表的并不是一个程序运行的时间，这并没有意义。而一个算法所花费的时间与其中语句的执行次数成正比，因此我们把算法中的基本操作的执行次数，称为算法的时间复杂度。
- 空间复杂度主要衡量一个算法所需要的额外空间。正如时间复杂度计算的不是时间，空间复杂度也不是计算程序占用了多少bytes的空间，因为这个也没太大意义，空间复杂度算的是变量的个数。
在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。 所以我们如今已经不需要再特别关注一个算法的空间复杂度。
二、时间复杂度
2.1 什么是时间复杂度
一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。
即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。
然我们看一道题目：
// 请计算一下Func1基本操作执行了多少次？ void Func1(int N) { int count = 0; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ++count; } } for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); }
我们通过分析得到Func1 执行的基本操作次数如下：
N = 10 ，F(N) = 130
N = 100 ，F(N) = 10210
N = 1000 ，F(N) = 1002010
显然如果直接用来表示时间复杂度的话会显得太过复杂。实际上我们发现随之N的不断增大，F(N)后续两项对结果的影响越来越小。因此我们在计算时间复杂度时，并不一定要计算精确的执行次数，只需求大概的执行次数，因此，就有了大O渐进表示法。
2.2 大O的渐进表达法
大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。
推导大O阶方法：
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中，只保留最高阶项。
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。
计算复杂度时，有时候会出现不同情况的结果，这时应该以最坏的结果考虑。
例如上述代码的时间复杂度就是O( 
)， 
就是我们求得的大O阶。我们用O( 
)表示当N趋于无穷大时，Func1()算法执行基本操作的次数约为 
次(后两项忽略不计)。
几个小例子：
------------------------------------------------>>> O(
)
------------------------------------------->>> O(
)
-------------------------->>> O(
)
2.3 一些常见的复杂度
我们常见的复杂度有以下几种：
第一级：O（1），O（logn）
第二级：O（n），O（nlogn）
第三级：O（
）,O（
），O（n！）
从上往下，从左到右，算法效率依次降低，下图为各种复杂度对于n的变化曲线：
实例1（O（1））：
// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }
操作执行了10次->O(10)
通过推导大O阶方法，常数的时间复杂度为 O(1)
实例2（O（logN））：
对数阶是一种比较快的算法，它一般每次减少一半的数据。我们常用的二分查找算法的时间复杂度就为O(logN)
// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; }
最好1次，
最坏log2（n)次，
时间复杂度为 O(logN)
| 第几次查询 | 剩余待查询元素数量 |
| 1 | N/2 |
| 2 | N/(2^2) |
| 3 | N/(2^3) |
| … | … |
| N | N/(2^N) |
ps:为何是logN 而不是log2 (N)
假如有logaB（a为底数），由换底公式可得：
logcA（c为底数）为常数，
由O的运算规则"O( C × f(N) )=O( f(N ) )，其中C是一个正的常数，得O（logaB）=O（logcB）
可知算法的时间复杂度与不同底数只有常数的关系，均可以省略自然可以用logN代替。
实例3（O（N））：
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }
通过计算分析发现基本操作递归了N次，时间复杂度为O(N)
实例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); } }
实例5（O（ 
））：
平方阶与线性对数阶相似，常见于嵌套循环中，每层循环的复杂度为O(N)
时间复杂度为O(N2)，最常见的就是冒泡排序
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; } }
实例6（O（ 
））：
指数阶的算法效率低，并不常用。
常见的时间复杂度为O(2N)的算法就是递归实现斐波拉契数列：
// 计算斐波那契递归Fib的时间复杂度？ long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }
- 值得一提的是斐波拉契的空间复杂度为O(N)，因为在递归至最深处后往回归的过程中，后续空间都在销毁的空间上建立的，这样能大大提高空间的利用率。
实例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; }
三、空间复杂度
空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。
// 计算Fibonacci的空间复杂度？ long long* Fibonacci(int n) { if (n == 0) return NULL; long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n; ++i) { fibArray[i] = fibArray[i - 1] + fibArray[i - 2]; } return fibArray; }
上面说到空间复杂度是统计变量的个数，因此通过分析得到Fibonacci() 创建的变量个数为：
F(n)=n+1+1
其中，n+1为malloc在堆上申请的空间，1为在栈上开辟的空间i（此处我们不考虑形参）。与时间复杂度相同，为了表达方便，空间复杂度同样采用大O的渐进表示法,通过保留最高项，去除常数项，我们得到Fibonacci()函数的空间复杂度为O(n）。
四、总结
1.时间复杂度计算的是基本操作执行次数，空间复杂度计算的是变量的个数，二者都采用大O渐进表示法。
2.时间/空间复杂度都是在最坏情况下所得到的。
3.时间一去不复返，是累积的；而空间是可以释放并重复利用的，是不累积的。
