前言🕵️‍♂️

在之前的学习中，已经接触过了网上OJ题目

在一些题目中，我们经常可以看到时间复杂度和空间复杂度的要求

你可能和我有一样的疑惑，复杂度究竟是什么？我要怎么评判我自己写的算法的复杂度？

今天就让我们来认识认识~~

1.算法效率🧐

和做任何事情一样，我们写的算法，自然也有它的运行效率。效率越高越好

1.1什么是算法

算法可以简单地理解为我们为了求解一个问题，所写的函数

在初识C语言中，我们学习过利用递归求解斐波那契数列的算法

1
2
3
4
5
6
7
long long Fib(size_t N)
{
     if(N < 3)
     	return 1;

     return Fib(N-1) + Fib(N-2);
}

这个算法只有3行代码，看上去非常简洁——但是简洁的代码不一定效率就高！

1.2如何衡量？

算法在编写成可执行程序的时候，main函数使用这个算法，需要调用一定的空间，消耗一定的时间。算法的效率就是通过空间和时间这两个维度来评判的

  • 时间复杂度：衡量一个算法的运行速度
  • 空间复杂度：衡量一个算法运行需要开辟的额外空间

2.时间复杂度⏰

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。算法中基本操作的执行次数，为算法的时间复杂度

  • 时间复杂度是一个近似值，并不是实际运行的时间
  • 实际上代码的运行时间，和机器的内存、cpu性能和平台都有关系，同一个代码在不同的机器上运行时间都不一样，如果只以纯粹的时间来考核，很难分析

找到某条基本语句与问题规模N之间的数学表达式，就算出了该算法的时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void test1(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++;
    }
    
    return;
}

请问这个代码中，count语句执行了几次？

可以总结出如下表格

NF(N)
10130
10010210
10001002010

你可能会简单地认为，F(N)的结果就是我们的时间复杂度。其实并不然，我们并不需要一个精确的运行次数，只需要知道程序运行次数的量级就行了

这里我们使用大O渐进表示法来表示时间复杂度（空间复杂度同理）

2.1大O的渐进表示法

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号

推导大O阶方法：

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中，只保留最高阶项。
  3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶

使用这种方法后，test1函数的时间复杂度为

对于test1函数，在计算的时候，我们省略了最后的+10，保留了最高阶数N2，即得出了它的时间复杂度

  • 如果最高阶数前面有系数，如2N，系数也将被省略

因为当N的数值很大的时候，后面的那些值对我们总运行次数的影响已经非常小了。大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数

2.1.1 O(logN)以什么为低

来自《代码随想录》2021年12月第1版 P13

在计算过程中，假设我们有如下两个时间复杂度
和
实际上，以2为底的O是可以转成以10为底的O

也就等同于
常数
总结出来就是

而在大O渐进法中常数可以忽略，所以我们可以认为log中的底数是意义不大的，可以忽略直接说logN

2.2多种情况取最坏

一些算法的时间复杂度会有最好、最坏和平均的情况

  • 最好情况：任意输入规模的最小运行次数(下界)
  • 平均情况：期望的运行次数
  • 最坏情况：任意输入规模的最大运行次数(上界)

举个例子，当我们编写一个在数组中查找数值的算法时，它可能会出现这几种情况：

  • 最好情况：1次就找到
  • 平均情况：N/2次
  • 最坏情况：N次

在实际中的一般情况，我们关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

2.3常见时间复杂度的计算

NO.1 双独立循环

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

这里出现了两个循环，分别是2N次和10次。前面提到了大O渐进法只保留最高阶数并省略系数，所以它的时间复杂度是O(N)

NO.2 双独立循环

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

这里出现了次数为N和M的两层循环

  • 当M和N差不多大的时候，时间复杂度可以理解为O(M)或O(N)
  • 当M远远大于N时，时间复杂度为O(M)
  • 一般情况取O(M+N)

NO.3 常数阶

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

这里我们得知了具体的循环次数为100，是一常数，时间复杂度为O(1)，代表常数阶

只要循环次数已知，为一常数且和所传参数无关，其时间复杂度即为O(1)

NO.4 strchr

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

看到这道题的时候，你可能会一愣，strchr是什么？

在之前的博客里，我介绍了很多常用的字符串函数👉点我

可这里面没有strchr，但有strstr

strstr函数的作用：在字符串1中寻找是否有字符串2

其中第二个str代表的是string字符串，那我们是不是可以猜想，chr代表的是char字符，其作用是在一个字符串中查找是否有一个字符呢？

当然，光是猜想肯定是不够的，我们还需要求证一下

如何查询库函数定义并尝试使用它？👉点我

打开cplusplus网站，搜索strchr，即可转到函数定义

image-20220313093417048

可以看到，该函数的作用是定位字符串中第一次出现该字符的位置，返回值是一个pointer指针

和我们猜想的一样，它的作用就是在字符串中查找一个字符，并返回它第一次出现的位置的地址。

这样一来，strchr函数的时间复杂度就很清楚了，就是遍历字符串所需要的次数，O(N)

NO.5 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
     }
}

冒泡排序是一个非常经典的代码，其思路就是遍历整个数组，如果待排序数字大于它的下一位，则交换这两个数字

  • N个数字的数组需要N-1次排序才能完成
  • 每一次排序都需要遍历一次数组

这样算来，冒泡排序的循环次数就是两个N相乘，即为O(N^2)

能否通过循环层级判断？

细心的你可能会发现，上述代码中出现了两层循环，那是不是可以通过循环层级来判断时间复杂度呢？

并不能！

1
2
3
4
5
for(int i=0;i<n;i++)
{
	for(int j=0;j<3;j++)
		printf("hehe\n");
}

如果是上述这种两次循环的情况，会打印3n次呵呵，其时间复杂度是O(N)而不是N^2

  • 我们要准确分析算法的思路，并不能简单地通过循环层级来判断时间复杂度

NO.6 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//a 数组，n长度，x需要查找的数
int BinarySearch(int* a, int n, int x)
{
     assert(a);
     int begin = 0;
     int end = n-1;
     while (begin <= end)
     {
         int mid = begin + ((end-begin)>>1);//使用位移操作符来模拟/2，防止begin和end相加后超出int范围
         if (a[mid] < x)
         	begin = mid+1;
         else if (a[mid] > x)
         	end = mid-1;
         else
         	return mid;//返回需要查找的数的下标
     }
     return -1;
}

二分查找的思路这里不再赘述

假设我们找了x次，每一次查找都会使查找范围减半

1
N/2/2/2/2 ……

最后我们可以得出2条公式

  • 最好情况：O(1)
  • 最坏情况：O(logN)

IMG_20220313_095703

通过时间复杂度的对比，我们就能看出二分查找的优势在那里了

NO(N)O(logN)
1000100010
100w100w20
10亿10亿30

可以看到，当数据很大的时候，O(logN)的算法执行次数比O(N)少了特别多!!（来自BT-7274的肯定）

img

NO.7 计算N!

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

     return Fac(N-1)*N;
}

对于这个阶乘的递归函数而言，每次函数调用是O(1)，时间复杂度主要看递归次数

对于数字N而言，递归需要N次，时间复杂度是O(N)

递归算法时间复杂度计算

1
递归算法时间复杂度 = 递归次数 * 每次递归中操作次数
  • 如果每次函数调用是O(1)，看递归次数
  • 每次函数调用不是O(1)，那么就看他递归调用中次数的累加

NO.8 斐波那契数列

计算斐波那契数可以用递归和迭代两种算法👉点我

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

     return Fib(N-1) + Fib(N-2);
}

每次递归，次数都会增加，总的来说是以2^x的量级增加的（x代表行数）

这里一共有x-1项，用等比数列的求和公式得出，结果为2x-1

所以最后得出的时间复杂度为O(2N)

需要注意的是，当递归调用到底部时，有一些调用会较早退出，这部分位于金字塔的右下角

IMG_20220313_103131

由于时间复杂度只是一个估算值，这一部分缺失的调用次数对总运行次数的影响不大，故忽略掉

NO.9 非+1递增循环

1
2
3
4
5
6
void fun(int n) 
{
   int i=l;
   while(i<=n)
      i=i*2;
}

此函数有一个循环，但是循环没有被执行n次，i每次都是2倍进行递增，所以循环只会被执行log2n次

NO.10 有序数组中查找和为sum的两个数

给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是？

1
2
3
4
A. O(n)//√
B. O(n^2)
C. O(nlogn)
D. O(logn)

数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n

NO.11 双嵌套循环

1
2
3
4
5
6
7
8
9
10
void test(int n)
{
    for(int i=0;i<n;i++)
    {//循环1
        for(int j=i;j<n;j++)
        {
            //循环2
        }
    }
}

以上是一个很常用的循环。其中循环2的执行次数是一个等差数列，第一次是n，第二次是n-1，第三次是n-2……一直到最后一次为1；

这个等差数列的求和为n(n+1)/2，即n2/2+n/2，因为时间复杂度需要取大且忽略系数，所以最终的时间复杂度为n2

3.空间复杂度🏠

3.1概念

空间复杂度是对一个算法在运行过程中临时占用空间大小的度量

和时间复杂度不是真的计算时间一样，空间复杂度也不衡量算法具体占用的内存字节数。

空间复杂度计算的是额外开辟的变量的个数，适用大O渐近法

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

3.2空间复杂度计算

NO.1 冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
     }
}

我们会发现，冒泡排序算法并没有额外定义非常多的变量，一共只有3个，属于常数阶

1
2
3
size_t end = n;
int exchange = 0;
size_t i = 1;

其空间复杂度为O(1)

计算时注意其与N的关系

当我们在算法中开辟空间，计算空间复杂度的时候，要注意开辟的这个空间与N有没有关系

1
2
3
4
int arr[N];//c99变长数组，和传过来的参数有关
int* a=(int*)malloc(sizeof(int)*N);//和传过来的参数有关，O(N)

int* a=(int*)malloc(sizeof(int)*3);//和传过来的参数无关，O(1)

NO.2 斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前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 <= n ; ++i)
     {
     	fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
     }
     return fibArray;
}

和上面的斐波那契数列的递归代码不同，这里我们新创建了一个数组，用来保存计算出来的斐波那契数

一共malloc了n+1个长整型的空间，空间复杂度是O(N)

函数栈帧空间重复使用问题

如果是递归方法的斐波那契算法，其空间复杂度是多少呢？

1
2
3
4
5
6
7
long long Fib(size_t N)
{
     if(N < 3)
     	return 1;

     return Fib(N-1) + Fib(N-2);
}

答案也是O(N)

因为对于递归算法而言，其开辟的函数栈帧空间是可以重复利用的！

如fib(8)的调用，其开辟的函数栈帧，是可以在后续继续调用fib函数时重复使用的

通过函数的参数压栈，我们可以很好地理解这是为啥👉点我

image-20220313113408340

上图中f1和f2是两个函数，但执行了相同的功能。其函数调用的空间实际上是一个，f2在f1销毁后继承了它的空间

这就好比每一次新的递归都会开一家新的饭店，但是你下次还想吃东北菜的时候，可以去之前开的东北菜馆，咱没必要让别人再开一家馆子不是嘛？

不过由于斐波那契数的递归算法会递归非常多次，在数字很大的时候，会导致栈溢出

image-20220313113142120

递归函数空间复杂度

针对递归函数，可以认为空间复杂度如下

1
递归层级 * 每次递归的空间复杂度

和时间复杂度的计算是很相似的。

比如下面这个斐波那契数列的空间复杂度，如果入参是5，调用会调用5层，每一层都是一个乘法操作，空间负载度是O(1)，最终得到的空间复杂度是O(5)，也就是O(N)

1
2
3
4
5
6
7
8
// 版本1
long long Fib(size_t N)
{
     if(N < 3)
     	return 1;

     return Fib(N-1) + Fib(N-2);
}

这个写法肯定不是最优的，代码随想录中提供了个更好的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
// 版本2
// 进入这个函数时，前两个参数都给1，N正常给
long long Fib(long long first,long long second,size_t N)
{
     if(N <= 0)
         return 0;
     if(N < 3)
     	return 1;
     else if(N == 3)// 相当于减少了两次递归
     	return first+second;
	
     return Fib(second,first+second,N-1);
}

此时减少了2次递归，虽然并没有降低空间复杂度（还是O(N))，但时间负载度大大降低！

  • 版本1时间复杂度为O(2n)
  • 版本2时间复杂度为O(N)

运行速度也会快非常多！

NO.3 阶乘

1
2
3
4
5
6
7
long long Fac(size_t N)
{
     if(N == 0)
     	return 1;

     return Fac(N-1)*N;
}

虽然函数本身的空间不计入时间复杂度，这里计算的是递归调用时额外开辟的函数栈帧空间

一共调用了N-1次，每个栈帧使用了常数个空间，空间复杂度是O(N)

4.常见复杂度对比👐

image-20220313113721007

image-20220313113801204

结语😘

时间复杂度和空间复杂度可以帮我们很好的了解自己所写算法的好坏，在未来面试的时候，HR肯定也更喜欢效率高的算法

要多刷题，好好积累自己的能力，想必之后写出好算法也是水到渠成（吧？）

如果这篇博客对你有帮助，点个赞再走呗~