时间复杂度和空间复杂度

前言：

       从今天开始，我们将正式进入数据结构这个专题，在数据结构中主要以：数组，指针，结构体为主。这三大模板未熟练的可以看看博主之前的文章，有一定基础的可以跟着继续学习。

       在数据结构中，有着众多的算法，比如查找算法，排序算法等。在查找算法中有顺序查找、折半查找、分块查找等，排序算法中有冒泡排序、快速排序、希尔排序等，而面对这么多的算法，是怎样去衡量算法的执行效率呢？而这也就是此篇文章的重点：时间复杂度和空间复杂度。话不多说，开始我们今天的学习吧。

一、什么是时间复杂度

       时间复杂度概念为：

       时间复杂度是一种衡量算法执行时间随输入规模增长而增长的速度的度量。它用大O符号（O）来表示，表示算法运行时间与输入规模之间的关系。时间复杂度描述了算法执行时间的增长趋势，而不是具体的执行时间。

        也就是说，计算机在运行在段代码时，你能知道运行了多少次吗？运行了多长时间吗？，所以，我们所计算的时间复杂度是基于最坏的情况进行计算的。那么，它的定义是什么意思呢？一言以蔽之，曰：算法中的基本操作的执行次数，为算法的时间复杂度。

二、什么是空间复杂度

       空间复杂度概念为：

       空间复杂度是衡量算法所需内存空间的度量。它表示算法在运行过程中所占用的存储空间大小。空间复杂度通常以数据结构的大小为基准，可以用来评估算法在处理大规模数据时所需的额外存储空间。

       注意： 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

三、计算时间复杂度

       我们在知道了概念后该如何计算时间复杂度呢？先来一个例子带大家来感受一下：

1. // 请计算一下Func1中++count语句总共执行了多少次？
2. 
3. void Func1(int N)
4. {
5.  int count = 0;
6. 
7.  for (int i = 0; i < N ; ++ i)
8.  {
9.    for (int j = 0; j < N ; ++ j)
10.     {
11.       ++count;
12.     }
13.   }
14.   for (int k = 0; k < 2 * N ; ++ k)
15.   {
16.     ++count;
17.   }
18.   int M = 10;
19.   while (M--)
20.   {
21.     ++count;
22.   }
23.   printf("%d\n", count);
24. }

       Func1 执行的基本操作次数 ： F(N) = N^2 + 2*N + 10。那么时间复杂度就为这么一推吗？在大家刷题时，大家也没见过这么复杂的时间复杂度，那么，时间复杂度该如何表示呢？

       这里，引进了大O的渐进表示法。

       3.1 大O的渐进表示法。

               大O符号：是用于描述函数渐进行为的数学符号。

               该如何理解呢？大家应该都学习过高数求极限，求解方法与之类似，即为抓大头：只看最高项。

推导大O阶方法：

        1、用常数1取代运行时间中的所有加法常数。

        2、在修改后的运行次数函数中，只保留最高阶项。

        3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

               按照这种理论，Func1的时间复杂度即为：N^2。

               另外有些算法的时间复杂度存在最好、平均和最坏情况。

                最坏情况：任意输入规模的最大运行次数(上界)

               平均情况：任意输入规模的期望运行次数

               最好情况：任意输入规模的最小运行次数(下界 ）

        那么，各个量级之间又有什么大小关系呢？如下：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)

       其实，这个关系可以与数学各个函数模型大小之间的类比：指数最大，常数最小。

       3.2 计算时间复杂度

               既然明白了关系，那么下一步就要明白如何计算。以下是几道例题。

              实例1

1. void Func1(int N)
2. {
3. int count = 0;
4. for (int k = 0; k < 2 * N ; ++ k)
5.      {
6.          ++count;
7.      }
8. int M = 10;
9. while (M--)
10.      {
11.          ++count;
12.      }
13. printf("%d\n", count);
14. }

              实例二

1. void Func2(int N, int M)
2. {
3. int count = 0;
4. for (int k = 0; k < M; ++ k)
5.      {
6.          ++count;
7.      }
8. for (int k = 0; k < N ; ++ k)
9.      {
10.          ++count;
11.      }
12. }

               实例三

1. void Func3(int N)
2. {
3. int count = 0;
4. for (int k = 0; k < 100; ++ k)
5.      {
6.          ++count;
7.      }
8. printf("%d\n", count);
9. }

              实例四

1. void BubbleSort(int* a, int n)
2. {
3. assert(a);
4. for (size_t end = n; end > 0; --end)
5.      {
6. int exchange = 0;
7. for (size_t i = 1; i < end; ++i)
8.          {
9. if (a[i-1] > a[i])
10.          {
11. Swap(&a[i-1], &a[i]);
12.              exchange = 1;
13.          }
14.      }
15. if (exchange == 0)
16. break;
17.  }

               实例五

1. int BinarySearch(int* a, int n, int x)
2. {
3. assert(a);
4. int begin = 0;
5. int end = n;
6. while (begin < end)
7.      {
8. int mid = begin + ((end-begin)>>1);
9. if (a[mid] < x)
10.          begin = mid+1;
11. else if (a[mid] > x)
12.          end = mid;
13. else
14. return mid;
15.      }
16. return -1;
17. }

              实例六

1. long long Factorial(size_t N)
2. {
3. return N < 2 ? N : Factorial(N-1)*N;
4. }

       接下来，就是振奋人心的解密答案环节了，答案分别为：O(N) 、O(M+N)、O(1)、O(N^2)、O(logN)(有些地方可能为：lgN)、O(N)。

       怎么样，这里简单解释一下吧。第一题时间复杂度应该为2N，因为执行2N次，但是取复杂度只看其量级，所以，时间复杂度为N。

       第二题，K分别执行N与M次，M与N之间的关系不确定，因此，时间复杂度为M+N次。

       第三题，因其K执行的次数为常数，所以，时间复杂度为1。

       第四题，本题考查冒泡排序时间复杂度，对于这种循环的嵌套，要剥洋葱来看，先看外层，外层循环次数为n次，内层循环是从1到n次对吧，那么一共循环（n*（n-1））/2（诸位大学生不至于连等差数列求和都看不明白吧🐶）。其内层循环量级为N^2,因此，该时间复杂度为N^2。

       第五题，本题考查二分查找时间复杂度，其最好情况为只找一次，最坏情况可以这样认为，每次都进行二次查找，可以想象成2^n的模型，对吧。设其查找次数为n，时间复杂度为logn（一般省略底数2，写成lgn也对），因此，时间复杂度为logN。

       第六题，本题一看为递归，一共递归N次，因此时间复杂度为N。

四、计算空间复杂度

       空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用 了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计 算规则基本跟实践复杂度类似，也使用大O渐进表示法。

       乍一看与时间复杂度计算类似，大白话讲空间复杂度看的是：为了解决这个问题多开辟出来的空间。

      来几道题来小试一下牛刀吧！

       实例一

1. void BubbleSort(int* a, int n)
2. {
3. assert(a);
4. for (size_t end = n; end > 0; --end)
5.      {
6. int exchange = 0;
7. for (size_t i = 1; i < end; ++i)
8.          {
9. if (a[i-1] > a[i])
10.              {
11. Swap(&a[i-1], &a[i]);
12.                  exchange = 1;
13.              }
14.          }
15. if (exchange == 0)
16. break;
17.      }
18. }

       实例二

1. long long* Fibonacci(size_t n)
2. {
3. if(n==0)
4. return NULL;
5. long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
6.      fibArray[0] = 0;
7.      fibArray[1] = 1;
8. for (int i = 2; i <= n ; ++i)
9.      {
10.            fibArray[i ] = fibArray[ i - 1] + fibArray [i - 2];
11.      }
12. return fibArray ;
13. }

      实例三

1. long long Factorial(size_t N)
2. {
3. return N < 2 ? N : Factorial(N-1)*N;
4. }

       老规矩：先公布答案：O(1)、O(N)、O(N）。

       第一题：咱们明白空间复杂度求的是为了解决这个问题多开辟出来的空间，来到这一题，本题求冒泡排序的空间复杂度，因其开辟的空间为常数个，因其空间复杂度为1。

       第二题：考查求斐波那契数列所开辟的空间数，为了解决这个问题开辟了一个数组，大家这时想一想，开辟这个叔祖是不是必须的，答案是否定的，不是唯一解法，所以答案是N。如果是唯一的，答案为1。这是为什么呢？注意重复出现的话语，空间复杂度求的是：为了解决这个问题锁额外开辟的空间数，如果为唯一解法，这个空间是不是必须开辟，不存在额外空间。所以，空间复杂度为1（注意：这是唯一方法，与本题无关了，本题答案是N）。

       第三题：本题为了解决递归这个问题多开辟出了N个空间，所以答案是N（递归可看作用空间换时间的做法）。

       本文到这里就结束了，如若有疑惑可私信也可在评论区留下疑问。

完！