前言🕵️‍♂️

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

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

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

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

1.算法效率🧐

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

1.1什么是算法

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

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

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之间的数学表达式，就算出了该算法的时间复杂度

void Test(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语句执行了几次？

N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010

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

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

2.1大O的渐进表示法

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

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

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

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

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

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

2.2多种情况取最坏

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

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

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

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

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

2.3常见时间复杂度的计算

NO.1 双独立循环

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 双独立循环

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 常数阶

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，即可转到函数定义

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

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

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

NO.5 冒泡排序

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)

能否通过循环层级判断？

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

并不能！

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

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

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

NO.6 二分查找

//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

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

N	O(N)	O(logN)
1000	1000	10
100w	100w	20
10亿	10亿	30

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

NO.7 计算N!

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
     if(0 == N)
     	return 1;

     return Fac(N-1)*N;
}

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

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

递归算法时间复杂度计算

如果每次函数调用是O(1)，看递归次数
每次函数调用不是O(1)，那么就看他递归调用中次数的累加

NO.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项，用等比数列的求和公式得出，结果为2^x-1

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

需要注意的是，当递归调用到底部时，有一些调用会较早退出，这部分位于金字塔的右下角
由于时间复杂度只是一个估算值，这一部分缺失的调用次数对总运行次数的影响不大，故忽略掉

NO.9 非+1递增循环

void fun(int n) 
{
   int i=l;
   while(i<=n)
      i=i*2;
}

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

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

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

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

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

NO.11 双嵌套循环

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，即n²/2+n/2，因为时间复杂度需要取大且忽略系数，所以最终的时间复杂度为n²

3.空间复杂度🏠

3.1概念

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

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

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

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

3.2空间复杂度计算

NO.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 < 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有没有关系

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

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

NO.2 斐波那契数列

// 计算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)

空间重复使用问题

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

long long Fib(size_t N)
{
     if(N < 3)
     	return 1;

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

答案也是O(N)

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

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

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

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

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

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

NO.3 阶乘

long long Fac(size_t N)
{
     if(N == 0)
     	return 1;

     return Fac(N-1)*N;
}

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

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

4.常见复杂度对比👐

结语😘

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

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

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