DS：时间复杂度和空间复杂度

欢迎各位来到 Harper.Lee 的学习世界！
  博主主页传送门：Harper.Lee的博客主页
  想要一起进步的uu欢迎来后台找我哦！
  

---

        本片博客重要介绍的是数据结构中关于算法的时间复杂度和空间复杂度的概念。
一、算法

1.1 什么是算法？

         算法(Algorithm):就是界说良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步调，用来将输入数据转化成输出效果。
1.2 算法的复杂度

        算法在编写成可执行步调后，运行时必要泯灭时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一样平常是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
        时间复杂度重要衡量一个算法的运行快慢，而空间复杂度重要衡量一个算法运行所必要的额外空间。在计算机发展的早期，计算机的存储容量很小。以是对空间复杂度很是在乎。但是颠末计算机行业的敏捷发展，计算机的存储容量已经达到了很高的水平，计算机的配置变得越来越高，对内存（空间复杂度）的关注也就没那么高了。以是我们如今已经不必要再特别关注一个算法的空间复杂度。目前计算机行业的硬件方面已经遇到瓶颈期了。
   摩尔定律：其焦点内容是当价格不变时，集成电路上可容纳的晶体管数目约每隔18个月至24个月便会增长一倍，同时性能也将提拔一倍。换言之，每一美元所能买到的电脑性能，将每隔18个月翻两倍以上。这一定律展现了信息技术进步的速度，为半导体行业的发展提供了长期的发展目标和预测。
  二、时间复杂度

2.1 时间复杂度的概念

        在计算机科学中，算法的时间复杂度是一个函数（这里的函数不是之前写的函数调用的那个函数，而是数学中的函数式），它定量描述了该算法的运行时间。一个算法执行所泯灭的时间，从理论上说，是不能算出来的，只有你把你的步调放在呆板上跑起来，才华知道。但是我们必要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，以是才有了时间复杂度这个分析方式。一个算法所泯灭的时间与其中语句的执行次数成正比例，算法中的基本操纵的执行次数，为算法的时间复杂度。即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。（时间复杂度越大，运行水时间越长）。
        但是我们为什么不直接讨论快速排序执行多少时间、冒泡排序执行多少时间呢？缘故原由在于具体怎么执行与自己的呆板（硬件）有关，硬件配置不一样，就不能比较具体执行的时间。因此，我么必要一套与环境因素（如硬件因素）无关的理论，也就是这里的时间复杂度。
请观察下面的代码，然后举行分析：
  

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

复制代码

Func1 执行的基本操纵次数 ：F（N）=N^2+2*N+10
N = 10              F(N) = 130，            N^2 = 100
N = 100            F(N) = 10210,           N^2 = 10000
N = 1000          F(N) = 1002010,       N^2 = 1000000
        从这个例子我们发现，当N越大（当N趋于无穷大时）,N^2对时间复杂度的效果影响最大。因此，我们选择大概估算（大O的渐进表现法）的方法，忽略掉2*N+10这一项，时间复杂度就可以表现为：F（N）=O（N^2）。当N很小的时候，认为时间复杂度一样，没有比较的意义，CPU主频很大。（CPU主频在 2.3 有具体介绍）
2.2 大O的渐进表现法

        大概估算是计算算法属于哪个量级（level）。
        大O符号（Big O notation）：是用于描述函数渐举行为的数学符号。
推导大O阶方法：
1、用常数1代替运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保存最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的效果就是大O阶。
利用大O的渐进表现法以后，Func1的时间复杂度为：F（N）=O（N^2）
        N = 10 F(N) = 100
        N = 100 F(N) = 10000
        N = 1000 F(N) = 1000000
        通过上面的分析，我们会发现大O的渐进表现法去掉了那些对效果影响不大的项，简洁明了的表现出了执行次数。
        别的有些算法的时间复杂度存在最好、均匀和最坏环境：
 最坏环境：恣意输入规模的最大运行次数(上界)
 均匀环境：恣意输入规模的期望运行次数
 最好环境：恣意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜刮一个数据x
 最好环境：1次找到
 最坏环境：N次找到
 均匀环境：N/2次找到
        在实际中一样平常环境关注的是算法的最坏运行环境，以是数组中搜刮数据时间复杂度为O(N)。
2.3 为什么O（n）利用最坏环境下的估算效果呢？

         在这种环境下，实际的效果要么就是估算的效果的惊喜，要么就刚好是最低预期效果，这是一种以防万一的心态，在预估了所有坏的可能后得到的方案。

2.4 CPU主频（拓展）

   CPU主频，也称为时钟频率或时钟速度，是指中央处理单位(CPU)内部时钟的频率或速度。
          它表现了处理器每秒钟执行指令的次数，通常以赫兹(Hz)为单位表现，例如兆赫兹(MHz)或千兆赫兹(GHz)。主频是评估其性能和速度的一个紧张指标之一。一样平常来说，较高的主频意味着处理器可以或许更快地执行指令，因此在一定水平上具有更高的性能。然而，主频并不是评估处理器性能的唯一因素，其他因素如微架构、焦点数目、缓存大小、指令集等也会影响性能。必要留意的是，主频并不是唯一影响处理器性能的因素。不同型号的处理器可能在相同主频下表现出不同的性能，由于它们的架构和其他规格可能不同。因此，在选择计算机或处理器时，不仅要考虑主频，还要综合考虑其他因素，以确保满足你的性能需求。
  （资料来自百度）
    CPU主频也叫时钟频率，单位是MHz，用来表现CPU的运算速度。
          CPU的工作频率（主频）包括两部门：外频与倍频，两者的乘积就是主频。
          倍频的全称为倍频系数。CPU的主频与外频之间存在着一个比值关系，这个比值就是倍频系数，简称倍频。倍频可以从1.5一直到23以至更高，以0.5为一个隔断单位。外频与倍频相乘就是主频，以是其中任何一项进步都可以使CPU的主频上升。由于主频并不直接代表运算速度，以是在一定环境下，很可能会出现主频较高的CPU实际运算速度较低的征象。因此主频仅仅是CPU性能表现的一个方面，而不代表CPU的团体性能 。
          处理器主频以每秒处理器周期可运行的百万次计算。通常，具有较高MHz或GHz的处理器可以或许进步电脑运行创新、娱乐、通信和生产力应用的性能。但主频只是影响体系团体性能的一个方面，主频高的呆板团体性能并非就一定高。
                        
（声明：此段文本复制自博客：http://t.csdnimg.cn/FGGi7）
          简而言之，CPU主频反映了在一个周期内大概能执行多少指令主频越高，CPU的处理速度越快。CPU性能再怎么差，它每秒的运算速度也能运行上亿次。可以利用clock函数验证：

1. #include <time.h>
3. int main()
4. {
5.         int begin1 = clock();
6.         int n = 100000000;
7.         int x = 10;
8.         for (int i = 0; i < n; i++)
9.         {
10.                 ++x;
11.         }
12.         int end1 = clock();
14.         printf("%d\n", x);
15.         printf("程序运行时间%d ms\n", end1 - begin1);
17.         return 0;
18. }

复制代码

​

如果效果为0ms阐明中央的时间斲丧小于1ms，而不是没偶然间斲丧。
        C语言中的函数clock()，它可以捕捉从步调开始运行到clock()被调用时所泯灭的时间。两个clock()函数的返回值相减，就可以计算两个函数之间的步调运行所斲丧的大概时间(ms)了。我么可以利用它来大抵测试一下电脑的性能。而且，release版本做了优化，因此时间比Debug版本稍短。

​
2.5 常见的时间复杂度量级

2.6 紧张时间复杂度计算

2.6.1 冒泡排序的时间复杂度 O（n^2）

        F（n）=（n-1）+ (n-2) + (n-3)+……+3+2+1=n*（n-1）/2 （可以根据两个数比较的次数来写）, 时间复杂度为：O（n^2）。留意不能直接数循环的个数。

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

复制代码

2.6.2 qsort函数的时间复杂度O（n*logn）

qsort函数的时间复杂度为： O（n*logn）


2.6.3 二分查找的时间复杂度

        折半查找：n，n/2，n/2/2，……，n/2/2/……/2（查找了x次就除以x个2）,2^x=N，以是x=logN（省略底数2）。最坏环境：查找区间只剩一个数或者找不到。O（logN）

1. // 计算BinarySearch的时间复杂度
2. int BinarySearch(int* a, int n, int x)
3. {
4.         assert(a);
5.         int begin = 0;
6.         int end = n - 1;
7.         // [begin, end]：begin和end是左闭右闭区间，因此有=号
8.     //保持左闭右闭区间（保持不变）
9.     while (begin <= end)//begin=end，还有一个数
10.         {
11.                 int mid = begin + ((end - begin) >> 1);//此写法可以防止溢出
12.                 if (a[mid] < x)
13.                         begin = mid + 1;//因为签】前一次比较中，mid已经比较过了
14.                 else if (a[mid] > x)
15.                         end = mid - 1;//end是mid-1
16.                 else
17.                         return mid;
18.         }
19.         return -1;
20. }
22. //写法二：
23. int BinarySearch(int* a, int n, int x)
24. {
25.     assert(a);
26.     int begin = 0;
27.     int end = n - 1;
28.     // [begin, end)  ->保持左闭右开区间
29.     while(begin<end)
30.     {
31.         //int mid = begin + ((end - begin) >> 1);//防止溢出（begin+end值可能很大）
32.         //也可以写成
33.         int mid = (begin + end)/2;(不能防止溢出)
34.         if (a[mid] < x)
35.             begin = mid + 1;
36.         else if (a[mid] > x)
37.             end = mid;//这里变成end=mid,而不是 mid-1
38.         else
39.             return mid;
40.     }
41.     return -1;
42. }

复制代码

        二分查找：O（logN），随着N的增长，O（logN）变化不大；暴力查找：O（N），随着N的增长，O（N）变化很大。
        缺点：二分查找外强中干，在实际中不太实用，必要排序、而且数组结构不方便插入删除数据（会造成数据团体的挪动）。
2.6.4  strchr函数的时间复杂度

1. // 计算strchr的时间复杂度？
2. const char * strchr ( const char * str, int character );

复制代码

        在一个字符串中查找一个字符，它的实现过程就相当于如下的代码：

1. while (*str)
2. {
3.         if (*str == character)
4.                 return str;
5.         else
6.                 ++str;
7. }

复制代码

        最好环境：O（1），最坏环境：O（n），均匀环境：O（（1+2+3+……+n）/n））。以是时间复杂度为O（n）。
        时间复杂度的意义：帮助我们对比几种解决方法孰优孰劣。 
三、 常见时间复杂度的举例

1、O（n）只看循环次数，且系数对效果影响不大

        F（n）=2*n+10 , O（n）而不是O（2*n）。F（n）相当于只看循环次数,要去掉系数2（即使这个系数是200也要去掉）,系数对效果影响不大，n无穷大时，n和2*n没有区别。

1. // 计算Func2的时间复杂度？
2. void Func2(int N)
3. {
4. int count = 0;
5. for (int k = 0; k < 2 * N ; ++ k)
6. {
7. ++count;
8. }
9. int M = 10;
10. while (M--)
11. {
12. ++count;
13. }
14. printf("%d\n", count);
15. }

复制代码

2、O（n）可以用多个未知数表现

        F（n）=M+N,  O（M+N）或O（max(M,N)。在时间复杂度，常常利用N作为未知数，也可以利用其它符号来表现未知数。如果M宏大于N，O(M)；如果如果N宏大于M，O(N)。不一定只有一个未知数。

1. // 计算Func3的时间复杂度？
2. void Func3(int N, int M)
3. {
4. int count = 0;
5. for (int k = 0; k < M; ++ k)
6. {
7. ++count;
8. }
9. for (int k = 0; k < N ; ++ k)
10. {
11. ++count;
12. }
13. printf("%d\n", count);
14. }

复制代码

3、F（n）= 常数,  O（1）

        时间复杂度是O（1），而不是O（100）。没有未知数而只有常数次，则时间复杂度为  O（1）。

1. // 计算Func4的时间复杂度？
2. void Func4(int N)
3. {
4. int count = 0;
5. for (int k = 0; k < 100; ++ k)
6. {
7. ++count;
8. }
9. printf("%d\n", count);
10. }

复制代码

4、只身狗题目回顾（为下一道题做铺垫）


5、力扣--17.04. 消散的数字

        题目描述：数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
思绪1：先排序（冒泡排序、qsort快速排序）再查找，如果前一个值(b)不便是后一个值(a) +1，那么前一个值(b)就是消散的数字。（由于时间复杂度，现可以直接扬弃该思绪）（排序：a，b; a+1==b），但时间复杂度不符合要求。

思绪2：先将0~N举行求和，然后再依次减去数组中值，剩下的值就是消散的数字。时间复杂度为O（N）。（缺陷：N太大，存在溢出风险）

1. int missingNumber(int* nums, int numsSize){
2.     int N = numsSize;//0~n一共n+1个数，但缺了1个数，一共n个数
3.     int ret = (0 + N) * (N + 1) / 2;//计算出0~n的总和
4.     for(int i = 0; i < numsSize; ++i)//
5.     {
6.             ret -= nums[i];//总和减去数组中值
7.     }
8.     return ret;
9. }

复制代码

思绪3：按位异或（相同为0，相异为1）（有点类似于只身狗的那道题）。O（n）

1. int missingNumber(int* nums, int numsSize){
2.     int N = numsSize;
3.     int x = 0;
4.     for(int i = 0; i < numsSize; ++i)//numsSize是少了1的，9个数
5.     {
6.         x ^= nums[i];//0和任何数异或均是任何数
7.     }  
8.     for(int j = 0; j <= N; ++j)//这里有n个数，10个数
9.     {
10.         x ^= j;
11.     }
12.     return x;
13. }

复制代码

6、力扣--189. 轮转数组

        题目描述：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 好坏负数。 
分析：必要一个循环两个嵌套，时间复杂度应该是：O（k*N）。
思绪1：暴力图解（用只管的方式直接解 决问题，不消太多技巧）
        表达式为：F（N）= （N-1）*（N-1）；O（k * N）
        如果k为7或者7的倍数次,旋转7次或者7的倍数次，实在就是旋转到原来的样子（相当于不旋转）；如果旋转10次，就相当于旋转了3次。以是真实的旋转次数为 k % = N ;在最好环境下，即没有旋转，k % N = 0 , O（1）;在最坏环境下K（N）=N*(N-1)， k % N = N-1，O（N^2）,旋转N-1次，。
        值得留意的是：时间复杂度必须要计算调用的其它方法所花的时间斲丧。

1. void rotate(int* nums, int numsSize, int k)
2. {
3.     k%=numsSize;
4.     while(k--)//k最大为n-1，k--走了k次，所以这里走了n-1次
5.     {
6.         //旋转一次      画图是最好的分析方法
7.         int tmp = nums[numsSize-1];//最后一个数保存起来
8.         for(int i =numsSize-2;i >= 0;i--)//起始位置在n-2（numsSize-2），结束情况：i >= 0
9.         {
10.             nums[i+1] = nums[i];//中间过程
11.         }
12.         nums[0] = tmp;
13.     }//但是用这种方法不能通过，超出时间限制（不能O（N^2））
14. }
16. //前n-1个数往后挪
17. //循环分析：循环就三个过程，起始情况、中间过程、结束情况

复制代码

        思绪2：三段逆置  O（N）

代码如下： 

1. void reverse(int*  a,int left,int right)
2. {
3.     //三段逆置一定要画图,下标标明
4.     while(left<right)//一段区间，左右往中间走，未相遇，交换值
5.     {
6.         int tmp =a[left];
7.         a[left] = a[right];
8.         a[right] = tmp;
9.         ++left;
10.         --right;
11.     }
12. }
14. void rotate(int* nums, int numsSize, int k) {
15.     k%= numsSize;
17.     reverse(nums,0,numsSize-k-1);//前n-k个数，最后一个下标n-k-
18.     reverse(nums,numsSize-k,numsSize-1);
19.     reverse(nums,0,numsSize-1);
20. }

复制代码

strncpy是针对字符串的，在这里不符合。
 
7、对数时间复杂度常见出现形式

        时间复杂度O（logN）

1. void func(int n)
2. {
3.     int x = 0;
4.     for (int i = 1; i < n; i *= 2)
5.     {
6.         ++x;
7.     }
8.     printf("%d\n", x);
9. }
10. int main()
11. {
12.     func(8);
13.     func(1024);
14.     func(1024*1024);
15.     return 0;
16. }

复制代码

        分析：1*2*2*……*2 = N；假设循环走x次，就是x个2相乘，2^x=N，双方同时取对数，得到

 。时间复杂度就是O（

）。由于写的时候必要支持专业公式，否则欠好写底数。为了方便 

省略了底数2，直接写成了

，但是其他的就不能省略且其他底数的很少出现。
8、阶乘递归的时间复杂度

1. // 计算阶乘递归Fac的时间复杂度？
2. long long Fac(size_t N)
3. {
4. if(0 == N)
5. return 1;
7. return Fac(N-1)*N;
8. }

复制代码

        每次调用函数都是O（1）的复杂度，调用N次就是O（N）的复杂度，而不是O（N！）。如果变式：时间复杂度为O（N^2）。 

2. //变式：
3. // 计算阶乘递归Fac的时间复杂度？
4. long long Fac(size_t N)
5. {
6.      if(0 == N)
7.      return 1;
8.      for(int i = 0; i <N;++i)
9.     {
10.         //……
11.     }
12.      return Fac(N-1)*N;
13. }

复制代码

        总结：递归时间复杂度为所有递归调用斲丧次数（相当于运算次数）的累加。
9、斐波那契递归和非递归的时间复杂度

        斐波那契递归非递归的时间复杂度O（N^2）

1. // 计算斐波那契递归Fib的时间复杂度？
2. long long Fib(size_t N)
3. {
4.  if(N < 3)
5.  return 1;
6.  
7.  return Fib(N-1) + Fib(N-2);
8. }

复制代码

        最左侧会逐步减少到Fib（1），有N层，但是右侧未必能走到N层，以是出现的三角形并不是等腰三角形，但是不影响最终的量级，大O阶表现时间复杂度O（N^2） 。分析过程如下图：

         斐波那契非递归（斐波那契数列的优化）的时间复杂度 ：

1. // 1  1  2  3  5  8....
2. // 时间复杂度：O(N)（很大的优化）
3. long long Fib(size_t N)
4. {
5.         long long f1 = 1;
6.         long long f2 = 1;
7.         long long f3 = 0;
8.         for (size_t i = 3; i <= N; i++)
9.         {
10.                 f3 = f1 + f2;
11.                 f1 = f2;
12.                 f2 = f3;
13.         }
15.         return f3;
16. }

复制代码

        实在斐波那契数列没什么特别的实用意义，由于数据稍稍大点就计算不出效果了。（50都不得行了）。别的，还可以利用字符串举行存储（大树运算）。
四、空间复杂度

4.1 空间复杂度界说 

        空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 
        空间复杂度不是步调占用了多少bytes的空间，由于这个也没太大意义，以是空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也利用大O渐进表现法。
        留意：函数运行时所必要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度重要通过函数在运行时候显式申请的额外空间来确定。
4.2 空间复杂度例题

        1、冒泡排序的空间复杂度

        变量个数：3（常数个），以是空间复杂度为O（1）。空间复杂度计算的是为相识决这个问题而额外初选的空间 ，因此此算法中的数组不计算空间。

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

复制代码

         2、  轮转数组另一个解法（空间复杂度）

        不消三段逆置的方法，重新创建一个数组，后k个旋转在前面，再把前n-k个拷贝到后面去 ，最后再将最终效果拷贝到原来的位置。此时，新创建的N个数组就是为相识决此问题而创建的，它就必要计算空间，空间复杂度就是O（N）。

最后的代码如下，代码中利用了变长数组：

1. void _rotate(int* nums, int numsSize, int k, int* tmp)
2. {
3.         k %= numsSize;
4.         int n = numsSize;
6.         memcpy(tmp, nums + n - k, sizeof(int) * k);
7.         memcpy(tmp+k, nums, sizeof(int) * (n-k));
8.         memcpy(nums,tmp, sizeof(int) * (n));
9. }
11. void rotate(int* nums, int numsSize, int k)
12. {
13.         int tmp[numsSize];
14.         _rotate(nums, numsSize, k, tmp);
15. }

复制代码

        3、阶乘递归的空间复杂度

1. // 计算阶乘递归Fac的空间复杂度？
2. long long Fac(size_t N)
3. {
4.         if (N == 0)
5.                 return 1;
7.         return Fac(N - 1) * N;
8. }

复制代码

4、斐波那契数列的空间复杂度为：



         常见的空间复杂度中只有三种：O（1）、O（N）、O（N^2）（比如二维数组）。

---

        创作不易，喜好的uu三连支持一下叭！ 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。