hello铁汁们，好长时间不见了，沉寂这么久是因为我也去提升自己了，好了，言归正传，我们在学习完C语言之后，就要开始学习数据结构了，因为在学习数据结构之前，你必须要拥有一种语言功底才能学好。现在，我们来学习数据结构的第一个知识点，求一段代码的时间复杂度和空间复杂度。
目录
1.时间复杂度和空间复杂度
首先，我们得知道什么是时间复杂度和空间复杂度，为什么会有这两个概念。这其实和我们的算法效率有关系，让我们首先来了解一下算法效率。
1.1算法效率
什么是算法效率，顾名思义，就是这个算法写出来运行的时间长短，那实现同一个功能，时间段的效率就高，时间长的效率就低。我们就是要来分析这个算法的效率高低。
1.算法效率分析分为两种： 时间效率、空间效率，它们分别对应的就是时间复杂度和空间复杂度。
2.时间复杂度主要衡量的是一个算法的运行速度
3.空间复杂度主要衡量的是一个算法运行所需要的额外空间
随着计算机容量越来越大，我们更关注于时间复杂度，但我们在学习时，都要学习
1.2时间复杂度
1.定义：在计算机科学中，算法的时间复杂度是一个函数，它定量的描述了算法的运行时间
2.我们要知道，一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度。
1.3空间复杂度
1.定义：对一个算法在运行过程中临时占用存储空间大小的量度
2.空间复杂度不是程序占用了多少字节的空间，它算的是变量的个数，计算规则基本和时间复杂度相似。
总结一下就是：时杂不算时间算次数，空杂不算空间算个数
那么我们怎么求时间复杂度和空间复杂度呢？这就引入了我们的大O渐进表示法。
2.大O渐进表示法
1.由来：大O这个符号是由由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著 作《解析数论》（Analytische Zahlentheorie）首先引入的，我们常用大O表示法表 示时间复杂度，注意它是某一个算法的时间复杂度。大O表示只是说有上界，它给 你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外， 一个问题本身也有它的复杂度，如果某个算法的复杂度到达了这个问题复杂度的下 界，那就称这样的算法是最佳算法。
这段话是什么意思呢？用我们通俗的话来说就是在我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要求出大概的执行次数，那么我们就使用大O渐进表示法。
2.大O符号：是用于描述函数渐进行为的数学符号。
3.大O渐进表示法的规则：
a.若只有常数项，用常数1取代运行时间中的所有加法常数，否则，常数可省略
b.在修改后的运行次数函数中，只保留最高阶项
c.如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶
4.这一点不算大O渐进表示法，但也可以算在其中，便于归纳总结，那就是，我们再求时间复杂度时，如果遇到复杂度不确定的情况，一般选用最坏的情况。
知道这些后，让我们看些例题来巩固这些知识
3.例题
3.1时间复杂度例题
罗列了不同情况下的时间复杂度的问题
1.求Func1的时间复杂度，也就是它执行了多少次？
void Func1(int N) { int count = 0; int i = 0; int j = 0; int k = 0; for (i = 0; i < N; i++) { for (i = 0; j < N; j++) { count++; } } for (k = 0; k < 2 * N; k++) { count++; } int M = 10; while (M--) { count++; } printf("count= %d \n", count); }我们要求时间复杂度，我们上面说过，时间复杂度求的是什么，它求的是代码执行的次数，所以我们现在来数一下它执行了多少次。
精确次数：for循环的嵌套（N*N次）+一个for循环（2*N次）+while循环（M=10次） =N^2+2*N+10
根据我们上面所学的大O渐进表示法，我们只要求出大概次数就是这个算法的时间复杂度，由大O渐进表示法我们可知，它可以省略常数项和低次项，只保留算法中的最高次项，也就是N^2。所以，这个算法的时间复杂度为： O(N^2)
我们还可以换一种理解方法，随着N的增大，这个表达式中N^2对结果的影响是最大的，时杂是一个估算，是去看表达式中影响最大的那一项，其他都可以省略，所以它的时杂是O(N^2)
2.求Func2的时间复杂度
void Func2(int N, int M) { int count = 0; int i = 0; for (i = 0; i < M; i++) { count++; } for (i = 0; i < N; i++) { count++; } printf("count= %d \n", count); }我们要求它的时间复杂度，这时我们发现会出现三种情况：
1.N和M的值确定不了谁大谁小，此时它的时间复杂度是：O(M+N)
2.M>>N,时间复杂度：O(M) 或者N>>M,时杂：O(N)
3.M与N差不多大，时间复杂度：O(M)或O(N)
3.求Func3的时间复杂度
void Func3(int N) { int count = 0; int N = 100; int k = 0; for (k = 0; k < N; k++) { count++; } printf(" %d \n", count); }我们可以看到，N已经告诉我们是多少了，它是一个常数项，根据大O渐进表示法，这个算法的时间复杂度就是：O(1)
4.计算Func4的时间复杂度
char* Func4(char* str, char character) { while (*str != '\0') { if (*str == character) { return str; } str++; } return NULL; }str中存放了字符串字符串的长度是N，假设是“abcdefg……”，character是我们要查找的字符
1.最好情况：假设查找a，那么我们只需要查找一次就查找到了，那么它的时间复杂度就是 O(1)
2.平均情况：查找字符串的中心g，我们就需要查找2/N次，它的时杂是O(2/N)
3.最坏情况：查找一个给定字符串中没有的字符或者字符串中的最后一个字符，此时，它的 时间复杂度就是O(N)
所以这道题的时间复杂度就是O(N)
所以，我们可以类推数组，在数组中搜索数据，它的时间复杂度为O(N)
5.求这个二分查找算法的时间复杂度
int BinarySearch(int* arr, int sz, int k) { assert(arr); int begin = 0; int end = sz - 1; while (begin < end) { int mid = (begin + end) / 2; if (arr[mid] < k) { begin = mid + 1; } else if (arr[mid] > k) { end = mid - 1; } else return mid; } return 0; }
它的时间复杂度也可以简写，因为很多地方不好写底数，所以二分查找的时间复杂度就是O（LogN），网上资料有时会写成O(LgN)，这是不对的，因为后者的底数是10，而不是2。
常见的时间复杂度就是O(N^2)，O(N)，O(LogN)，O(1)
3.2空间复杂度的例题
罗列了不同情况下的空间复杂度的问题
1.计算BubbleSort（冒泡排序）的空间复杂度
void BubbleSort(int* a, int size) { assert(a); int i = 0; int j = 0; for (i = 0; i < size - 1; i++) { int flag = 0; for (j = 0; j < size - i - 1; j++) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; flag = 1; } } if (flag == 0) { break; } } }我们要求它的空间复杂度，我们在上面说过，求空间复杂度也用大O渐进表示法，空间复杂度求的是变量的个数，所以我们分析一下：
我们发现它有六个变量，根据大O渐进表示法，它的空杂为O(1)，到这大家可能会有一个疑问，它循环了那么多次，为什么不算空间，因为只有时间是累计的，空间是不累计的，循环走了不管多少次，它重复利用的是一块空间。
2.求fib（斐波那契算法）的空间复杂度
int* Fib(int N) { if (N== 0) { return NULL; } int* fib = (int*)malloc(sizeof(int)*N); if (fib == NULL) { perror("malloc"); exit(-1); } fib[0] = 0; fib[1] = 1; int i = 0; for (i = 2; i < N; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib; }我们求它的空间复杂度，除去那些常量的变量个数，我们malloc了一块N个大小的空间，此时省略那些对空间影响不大的，我们的空间复杂度就是O(N)。
所以，我们得到：开辟常数个空间，它的空间复杂度为：O(1)
malloc一块大小不定的空间，它的时间复杂度为：O(N)
3.求递归的时间复杂度
int Fac(int N) { return N < 2 ? N : Fac(N - 1) * N; }这里我们使用了递归，我们分析，递归一次建立一个函数栈帧，每个栈帧使用了常数个空间，然后这里我们调用了N次，通常我们认为它的空间复杂度就是N了，但其实不然，我们函数在调用时建立函数栈帧，但在调用结束时会销毁这个栈帧，我们在前面也说过空间是不累计的，它重复利用的是一块空间，所以，它的空杂还是O(1)。
好了铁汁们，今天的分享就到这里，时间复杂度和空间复杂度其实是很简单的，觉得难可能是因为第一次接触这个概念，我们下来常看勤做练习，很快就融汇贯通了，谢谢大家的品读，我们下期再见！！！
