数据结构（C）：时间复杂度和空间复杂度
目录
🚀 0.前言
🚀 1.为何会有时间复杂度和空间复杂度的概念
🚀 2.时间复杂度
2.1初步时间复杂度
2.2大O表示法
2.2.1.O（N*N）
2.2.2.O（N）
2.2.3.O（1）
2.3最坏情况？
2.3.1O(N*N)
2.4递归
2.4.1O（N）
2.4.2O(2^N)
🚀 3.空间复杂度
3.1O（1）
3.2 O（N）
🚀4.结束语
🚀 0.前言
言C之言，聊C之识，以C会友，共向远方。各位CSDN的各位你们好啊，这里是持续分享数据结构知识的小赵同学，今天要分享的数据结构知识是时间复杂度和空间复杂度，在这一章，小赵将会向大家展开聊聊何为时间复杂度，何为空间复杂度。✊
🚀 1.为何会有时间复杂度和空间复杂度的概念
其实为何会有这两个概念呢？其实很简单，就像我们人类的工作吧，老板在挑选工作的时候总会挑选那些工作效率高（即用时少），给工资低的人，来作为自己的员工。因为挑选这样的人做自己的员工可以让自己的利益最大化。而我们的计算机在写程序的时候也一样，我们要让自己的程序最好，那么就要降低它的工作时间和占用空间的大小。由此引申出两个概念时间复杂度和空间复杂度。而这两个东西又该如何去看呢？别急小赵下面一一介绍。
🚀 2.时间复杂度
2.1初步时间复杂度
什么叫时间复杂度呢？其实就是程序运行次数的极限。那固定的次数有极限吗？答案当然是没有啦，所以我们的所有固定次数的程序是最容易看出时间复杂度的。虽然我们在学的时候往往会将它们归向程序的时间复杂度较低的一列，但如果运行次数过多，那它的时间复杂度也是很恐怖的，那什么时候就很多了呢？请看下面的代码：
for (int i = 1; i a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
看到这个程序，很多人会一口直出，这不简简单单， O（N*N），但实际上很多人并不理解为什么是这个答案。那么是这个答案的原因是什么呢？其实是因为我们在看计算机的程序运行次数的时候，往往考虑的其实是他的最差情况，那么这样也就好理解这个答案，按我们去算这个最坏就是每个数字都要换，用数学方法算出来就是(N*(N+1)/2次，然后我们去掉数字，就是N*N，所以这题的结果就是O（N*N）。而这样的时间复杂度其实也决定了冒泡排序不是我们主流的排序方法，因为其的时间复杂度太大。
2.3.1O(log N)
看完了冒泡排序，我们再来看看我们的二分查找。
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
while (begin >1);
if (a[mid] x)
end = mid-1;
else
return mid;
}
return -1;
}
二分查找的最坏情况是logN次所以其的时间复杂度是O（logN），这个时间复杂度是很小的，二分查找也是我们在查找数字常用的算法，但是其必须要求数组是已经排好的，这让他有了局限性。
2.4递归
好了看惯了循环，给各位换换胃口，我们看看递归的时间复杂度该如何看：
2.4.1O（N）
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
这个代码我们只要一直向下迭代就会发现最后其实是运行了N次，那么其的时间复杂度就是 O（N）；
2.4.2O(2^N)
long long Fib(size_t N)
{
if(N
这个递归就相对比较复杂了，也是我们后面二叉树时候将要面对的难题，这里我们我们用递归展开图神器解决
我们对这个代码进行估算，最后会发现我们这个代码最多运行2的N次方-1，那么其的时间复杂度就是O(2^N)。
好了时间复杂度到这里就结束了，相信各位已经能够熟练掌握了，为自己再掌握一个知识点欢呼。
🚀 3.空间复杂度
了解了时间复杂度，其实空间复杂度就很简单了，因为这两个都是用的大O表达式，而这里就是吧运行次数改成你这个程序在运行时开辟的额外空间。
直接举例子吧。
3.1O（1）
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 a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
以冒泡排序举例，x，我们就定为O(1)（或者开辟几个固定空间跟前面一样）。
3.2 O（N）
long long* Fibonacci(size_t 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 
