1. AI技术聚合首页
  2. IT

手把手带你了解时间复杂度和空间复杂度 【超详细】

社会演员多 • • IT • 阅读 48

目录

前言

学习数据结构的第一步，对时间复杂度和空间复杂掌握和理解是非常关键的，不管是考研还是学校的应试或者说你想要写出一个效率高的程序，内容有点多，请大家耐心看完

为什么要学习复杂度？

一个问题会有多种解法，我们需要对算法的优劣进行判断，哪种是最优的，这时候我们需要对复杂度有一定程度的了解

如：斐波那契数列的两个实现方式，一种递归，一种循环

递归：

 循环：

两种解法的分析在实例8和实例9

一、 算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间复杂度主要衡量的是一个算法的运行次数，而空间复杂度主要衡量一个算法所需要的额外空间，在摩尔定律下，现在计算机的存储容量达到很高的程度，反而我们现在最需要关注的就是一个算法的时间效率。

一个算法源文件(.c)经过编译、链接后生成可执行文件(.exe)后，运行时会对计算机造成一定的资源消耗，时间消耗是对CPU的处理速度，空间消耗是对内存栈区(Stack)的空间

总结：衡量一个算法的好坏，就是从时间和空间两个维度来衡量。

二、时间复杂度

2.1时间复杂度概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

说明下很多理解时间复杂度是这样，顾名思义嘛，就是时间复杂度就是一个算法执行完成的所需要花费的时间嘛，错误

简单的举个例子：

假如大主播马斯托5w的主机：4090 + 华硕ROG主板 + i9 13900K + 64G内存和你一个上古世纪志强CPU + 军工级主板 + 集显  + 2G内存的洋垃圾打开一个网站都卡成PPT的主机比哪个运行速度快，你说说看怎么比，因此上世纪的科学家，就定义出一个专门衡量程序好坏的方法。

很多朋友看到这里就觉得自己懂了，那我们来试试吧

2.1大O的渐进表示法

// 请计算一下Func1基本操作执行了多少次？
void Func1(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;
	}
	printf("%d\n", count);
}

Func1函数是有三个循环组成，由上面讲的可以得知，执行了多少次就是我们想要的时间复杂度

  • 第一段嵌套for循坏执行次数是N^{_{2}} 就是 N * N，因为有两层循环，第一层和第二层都是走到N才能停止
  • 第二段for循坏执行次数是 2 * N，因为K = 0 要递增到 2 * N才能停止
  • 第三段while循环执行次数是 10，因为 M = 10，M进入循环递减到0，才能停止
  • 所以F(N) = N² + 2 * N + 10

但是实际中我们计算时间复杂度时，我们并不需要计算准确的执行次数，只需要大概执行次数，这里我们用大O的渐进表示法。

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

推导大O阶方法：

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

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

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

使用大O的渐进表示法以后，Func1的时间复杂度为：O(N²)

通过大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。

我们就拿刚才的Func1来举例

  • N = 10         F(N) = 10 * 10 + 2 * 10 + 10 = 130               此时最高项数是100，较低项数和是30
  • N = 100       F(N) = 100 * 100  + 2 * 100 + 100 = 10300    此时最高项数是10000，较低项数和是300  

当N越来越大的时候不是最高阶项数对结果影响会越来越小

总结：大O的渐进表示法就是看程序在那个阶级的

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

  • 最坏情况：任意输入规模的最多运行次数
  • 平均情况：任意输入规模的期望运行次数
  • 最好情况：任意输入规模的最少运行次数

请大家一个例子，在数组中找一个数x，请大家下面程序

数组长度为9，数字存放的位置是0 – 8

int FindNum(int *arr, int len, int x) {
	for (int i = 0; i < len; i++) {
		if (arr[i] == x)
			return i;
	}
	return -1;
}

int main() {
	int arr[] = { 11,22,33,44,55,66,77,88,99 };
	int len = sizeof(arr) / sizeof(int);
	int f = FindNum(arr, len, 11);		// 最好情况：数组的第一个就找到了
	int m = FindNum(arr, len, 55);		// 平均情况：数组的一半找到了
	int l = FindNum(arr, len, 99);		// 最坏情况：数组的最后才找到

	printf("最好情况数组下标：%d\n", f);
	printf("平均情况数组下标：%d\n", m);
	printf("最坏情况数组下标：%d\n", l);

	return 0;
}

输出结果

最好情况：1次就找到

最坏情况：N次找到

平均情况：N/2次找到

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

2.2常见时间复杂度计算举例

 实例1：

// 计算Func2的时间复杂度？
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

分析：

k = 0，k要递增到 k = 2 * N，才能结束

m = 10；要执行10次，所以精确执行次数是2N + 10

用大O渐进表示法最后时间复杂度是O(N)

 实例2：

// 计算Func3的时间复杂度？
void Func3(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);
}

分析： 

第一个for循环k = 0，k < M，需要执行M次才能结束

第二个for循环k = 0，k < N，需要执行N次才能结束

只是在M和N不确定谁大情况下，时间复杂度是O(M + N)

M和N相等，时间复杂度是O(M) 或者 O(N)

M远大于N，时间复杂度是O(M)

N远大于M，时间复杂度是O(N)

实例3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

分析：

k = 0，要递增到100的时候循环才能停止

有很多人就觉得结果是O(100)，错误，时间复杂度里面就没有这种说法

我们看到一个明确的次数，都要把它看成O(1)

这里不是循环只跑了1次，而是常数(明确)次数

所以时间复杂度是O(1)

实例4：

// 计算strchr的时间复杂度？
const char* strchr(const char* str, char character)
{
	while (*str != '\0')
	{
		if (*str == character)
			return str;

		++str;
	}

	return NULL;
}

分析：

看最坏情况，要么是找字符串最后一个或者就是没有找到

时间复杂度是O(N)

实例5：

// 计算BubbleSort的时间复杂度？
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;
	}
}

分析：

冒泡排序很多人都知道时间复杂度是O(N^{2})，我们来来它是怎么来的呢

错误想法：不要看有x个循环套着，就是O(N^{x})

我们需要分析循环的执行条件

要对N – 1个进行排序，每次还需要交换N – 1，N – 2，N – 3，…… 2 ，1

我们把次数相加，等等这怎么有点像等差数列，公差是1，首项是N – 1，尾项是1，项数是N – 1

现在我们就可以用数列的求和公式：\frac{(N-1)+1*(N-1)}{2}

省略掉不重要的项数，大O渐进表示法O(N^{2})

最好情况是O(N)

如：2,1,3,4,6,5，只需要交换N – 1次

实例6：

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

分析：

二分查找的最好情况是O(1)，折半第一次的时候的正好就找到了

最坏情况是找最左边或者最右边，还有就是找不到

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

折半了几次，就是查找了几次

设折半了x次

2^{_{x}}  = N，x = {log_{2}}^{N}

所以时间复杂是O({log_{2}}^{N})

刚才我们分析了二分查找的时间复杂度，就可以根据数组长度，得出查找次数

  • 在数组里面有1000个有序数字里面查找x，需要多少次呢？

套上面的时间复杂度公式最多要找10次，因为2^{10} =  1024, 2^{x}必须要大于N，1024 > 1000，所以是10次，9次就不行了，2^{9}是512， 512 < 1000

  • 在数组里面有14亿个有序数字里面查找x，需要多少次呢？

最多需要找31次，2^{10}是1024，2^{20}是1024 * 1024，2^{30}是1024 * 1024 * 1024，我们可以大概看成+10次方就是给后面添3个0，10 2400 0000 * 2 大约就是20亿

实例7：

// 计算阶乘递归Factorial的时间复杂度？
long long Factorial(size_t N)
{
 return N < 2 ? N : Factorial(N-1)*N;
}

分析：

递归算法：递归次数 * 每次递归调用的次数

递归了N次，每次调用了2次，其中比较了1次，还有最后return的时候计算了1次，所以是常数次，所以是N * 常数次，还是O（N）

N * (N – 1) * (N – 2) * (N – 3)  ……   * 1 ，逐步向下递归，递归了N次

时间复杂度是O(N)  

 实例8:

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

 分析:

递归算法：递归次数 * 每次递归调用的次数

每次递归调用的次数是O(1)，所以我们就看递归次数

递归总次数：Fib(N) = 2^{0}+2^{1}+2^{2}+......+2^{N-1} -X   

我们把X先省略，这就是一个公比为2的等比数列

运用等比数数列求和公式，a1 = 1，an = 2^{N-1}，q = 2,\frac{1*(1-2^{n}))}{1-2}

结果等于：2^{N}-1，把X加上去2^{N}-1-X，但是X远小于2^{N}

最后1和X省略，时间复杂度为O(\large {\color{Red} 2^{N}})

 实例9:

// 计算斐波那契循环Fib的时间复杂度？
long long Fib2(size_t N)
{
	long long* arr = (long long*)malloc(N * sizeof(long long));
	arr[0] = arr[1] = 1;
	
	int i;
	for (i = 2; i < N; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	long long val = arr[i - 1];
	free(arr);
	return val;
}

分析：

循环斐波那契时间复杂度是O(N)

当i递增到等于N，循环就会停止，前2项 + 前1项得到当前项，就这样一直循环，根据和上面递归斐波那契相比，写斐波那数列时候还是建议用循环的方法

说到这里想必大家对时间复杂度肯定有点一定的了解，那我就在给大家看个特殊的题

x = n;	// n是不小于1的常数
y = 0;
while (x >= (y + 1) * (y + 1))
{
	y++;
}

分析：

此程序时间复杂度是​​​​​​​，平方根阶

这个时间复杂度比O({log_{2}}^{N})慢，比O(N)快

这是一个不常见的时间复杂度,y^{2} <= x 等于 y <= \sqrt{x}，循环一次y++

三、 空间复杂度

3.1空间复杂度的概念

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

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

总结：一个程序运行需要额外定义变量个数

3.2常见空间复杂度的计算

 实例1：

// 计算BubbleSort的空间复杂度？
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;
	}
}

分析： 

有三个变量临时分别是exchange，i，end，一共3个额外的空间

i在第二层循环里，这个循环要执行n次，但是循环n次里面的i都是一个空间

在内存栈区，创建在销毁，创建在销毁

可以看上图，每次输出刚进循环的i，地址都是一样的。
空间复杂度是O(1)

实例2：

// 计算Fibonacci的空间复杂度？
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;
}

分析：

开了一块n+1的个数的数组空间，省略掉一些不影响的项数

i和上面冒泡一样都是同一个空间

空间复杂度是O(N)

实例3：

// 计算阶乘递归Factorial的空间复杂度？
long long Factorial(size_t N)
{
    return N < 2 ? N : Factorial(N-1)*N;
}

分析： 

递归调用了N次，每次调用都建立了一个栈帧

空间复杂度是O(N)

 实例4：

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

分析：

先调用Fib(N-1)，递归到Fib(1)，创建了N个栈帧空间

然后返回，中间的栈帧空间返回的时候就全部销毁

还是那个概念，空间的复用，创建了在销毁

在Fib(N-2)递归的时候，递归的过程还是之前的空间

空间是可以重复利用，不累计的

而时间一去不复返，累计的

空间复杂度是O(N)

测试：调用函数，创建栈帧空间，运行结束了，空间在销毁 ，在调用函数，创建，运行，结束，销毁。

 a用完了结束，b再用，用完c在用，3个函数的变量都指向同一地址

三、常见复杂度对比 

四、复杂度OJ练习题 

 4.1 消失的数字OJ链接：https://leetcode-cn.com/problems/missing-number-lcci/

1. 相减法                时间：O(N)        空间：O(1)

思路：数组nums包含从0到n的所有整数，但其中缺了一个，我们把0-n的整数相加，依次减去数组nums中每个整数，最后结果就是缺失的数

int missingNumber(int* nums, int numsSize){
    int sum = 0;
    
    // 0-n的和
    for (int i = 0; i <= numsSize; i++)
        sum += i;

    // sum依次减去数组中的整数
    for (int i = 0; i < numsSize; i++)
        sum -= nums[i];

    return sum;
}

2. 标记法                时间：O(N)        空间：O(N)

思路：开辟一块n+1的空间，用来存放0-n，把所有的值全部赋值-1，然后把数组nums里面的数放到开辟数组arr对应的下标位置，如a[0]放0，a[1]放1……最后缺失的数字值是-1，返回值为-1的下标

int missingNumber(int* nums, int numsSize){
    int *arr = (int*)malloc((numsSize + 1) * sizeof(int));  // 开辟一个numSize+1的空间，+1是因为缺少一个元素

    // 把开辟的数组里面全部赋值为-1
    for (int i = 0; i <= numsSize; i++)
        arr[i] = -1;
    
    // 把nums数组里面的值拷贝到arr数组对应的位置，如0放到arr[0]，1放到arr[1]
    for (int i = 0; i < numsSize; i++)
        arr[*(nums + i)] = nums[i];
    
    // 遍历数组，值为-1的就是缺失的，返回数组下标
    for (int i = 0; i <= numsSize; i++)
        if (arr[i] == -1)
            return i;
   return 0;
}

3. 异或法                时间：O(N)        空间：O(1)

思路：异或是相同为0，不同为1，比如：3 ^ 3结果是0，0 ^ 6结果是6，我们可以创建一个x值为0，用它来与和0-n的数异或，然后再和数组nums里面所有的值异或，最后x的结果就是缺失的数字

比如：4，2，3，3，4，x依次异或这一串数字，x就是2，两个相同的数字就是0，0和一个数异或，结果就是一个数

int missingNumber(int* nums, int numsSize){
    int x = 0;  // 用来异或
    
    // 用x先与0-n的数异或
    for (int i = 0; i <= numsSize; i++)
        x ^= i;
    
    // 再用x与数组nums里面的所有数异或，相同的数就是0
    for (int i = 0; i < numsSize; i++)
        x ^= nums[i];

    return x;
}

4.2 旋转数组OJ链接：https://leetcode-cn.com/problems/rotate-array/

1. 暴力求解法                时间：O(N * K)        空间：O(1) 

思路：一次旋转向右1个数（把最后的数移动到下标0的位置），旋转K次。

1.先把最后的数放到一个临时的变量里

2.然后从下标0的数到下标numSize – 1的数，依次向后移动一次

3.把存放最后的数赋值到下标0的位置

但是力扣测试样例通过不了，会超时，因为有的测试样例，需要旋转的数特别多

void rotate(int* nums, int numsSize, int k){
    // k个数旋转，就要旋转k次，1次旋转1个数
    for (int i = 1; i <= k; i++) {
        int end = numsSize - 1;
        int tmpEnd = nums[end];
        // 从倒数第2的数字开始分别向后移1位
        for (end = numsSize - 1; end > 0; end--) {
            nums[end] = nums[end - 1];
        }
        nums[0] = tmpEnd;   // 把最后一个元素赋值到第0的位置
    }
}

2. 开辟法                时间：O(N)        空间：O(N)

思路：

1.开辟一个和数组nums长度一样的数组

2.从tmp数组第k个下标开始赋值nums第0个位置的值，可以正好是旋转后的数据，但是这样赋值k + i > numSize就会造成越界，这里只需要(k + i) % numSize，k + i加起来大于numSize就会从头赋值，这里不好说明，大家可以试着代入数分析下，就知道什么意思了

3.把旋转完成的数组tmp的值赋值给数组nums，题目意思是对数组nums操作

void rotate(int* nums, int numsSize, int k){
    // 开辟长度和nums一样数组
    int *tmp = (int *)malloc(numsSize * sizeof(int));   

    // 
    for (int i = 0; i < numsSize; i++) {
        tmp[(k + i) % numsSize] = nums[i];
    }
    // 把tmp数组所有元素赋值到nums数组
    for (int i = 0; i < numsSize; i++) {
        nums[i] = tmp[i];
    }
}

3. 分步翻转法                时间：O(N)        空间：O(1)                最优

思路：

1.翻转前n – k数

2.翻转后k个数 

3.翻转全部数

void reverse(int *arr, int begin, int end) {
    // begin到end的逆置
    while (begin < end) {
        int t = arr[begin];
        arr[begin] = arr[end];
        arr[end] = t;
            
        begin++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;  // 特殊情况 k > numsize就会越界

    reverse(nums, 0, numsSize - k - 1);  // 逆置前numSize - k个
    reverse(nums, numsSize - k, numsSize - 1);   // 逆置后k个
    reverse(nums, 0, numsSize - 1);  // 逆置整个数组
}

这篇文章能给你带来帮助，这就是我最大的快乐，文章有错误地方或建议请指出，看到立马改正，谢谢

版权声明：本文为博主作者：橡皮擦Eraser原创文章，版权归属原作者，如果侵权，请联系我们删除！

原文链接：https://blog.csdn.net/tuweizhiwang/article/details/129714398

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
社会演员多的头像社会演员多普通用户
0
上一篇 2024年1月3日
下一篇 2024年1月3日

相关推荐