【数据结构】时间复杂度和空间复杂度的计算

绝地灬酷狼 2023-09-26 18:36 141阅读 0赞

**目录**

算法的复杂度

时间复杂的的概念

时间复杂度计算方法

大O的渐进表示法

空间复杂的概念

空间复杂的的计算方法

时间和空间复杂度的应用

消失的数字

轮转数组

--------------------

## 算法的复杂度 ##

![e07dc75556f94b459906f08587a2c895.png][]

算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，及时间复杂度和空间复杂度。

时间复杂度主要衡量-个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

## 时间复杂的的概念 ##

时间复杂度的定义:在计算机科学中，算法的时间复杂度是一个函数， 它定量描述子该算法的运行时间。一个算法执行所耗费的时间，从理论上说，不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例， 算法中的基本操作的执行次数，为算法的时间复杂度。

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

### 时间复杂度计算方法 ###

> 请计算一下Func1中++count语句总共执行了多少次？

void Func1(int N)
    {
    	int count = 0;
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < N; j++)
    		{
    			++count;
    		}
    	}
    	for (int j = 0; j < N; ++j)
    	{
    		++count;
    	}
    	int M = 10;
    	while (M--)
    	{
    		++count;
    	}
    	printf("%d\n", count);
    }

我们可以分开来求Func1中++count的执行次数，Func1中有三重循环 ，第一重循环为嵌套的for循环。

在第一重循环中 执行++count的次数为 N\*N 次

在第二重循环中 执行++count的次数为 N 次

在第三重循环中 执行++count的次数为 M 次,其中 M=10

由此得出时间复杂度的函数式： F(N)=N^2+2\*N+10

通过这个时间复杂度的函数式，我们发现当N越大，后两项对结果的影响是越小的：

![d21c72e695a24d34b4799b2aaefad898.png][]

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数,那么这里我们使用大O的渐进表示法

#### 大O的渐进表示法 ####

**大O符号(Big O notation) : 是用于描述函数渐进行****为的数学符号。  
推导大O阶方法:**  
1、用常数1取代运行时间中的所有加法常数。  
2、在修改后的运行次数函数中，只保留最高阶项。  
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数，得到的结果就是大O阶。

> 实例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);
    }

首先，根据上个例子，我们可以轻松得到Func2的精确时间复杂度的函数式：F(N)=2N+10

再根据大O的渐进表示法，去掉与这个项目相乘的常数2和加法常数10，最后得到它的空间复杂度为： 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);
    }

这道题并没有说明M和N的大小关系，因此时间复杂度为 ：O(M+N)

但是：

如果M远大于N ，我们可以认为时间复杂度就是 O(M);

如果M远大于N ，我们可以认为时间复杂度就是 O(N);

如果M和N的大小近似，我们可以认为时间复杂度是 O(N)或者是O(M);

**特别提示：一般情况下时间复杂度计算时未知数都是用的N，但是也可以是M、K等等其他的**

> 实例3：计算Func2的时间复杂度？

void Func4(int N)
    {
    	int count = 0;
    	for (int k = 0; k < 100; ++k)
    	{
    		++count;
    	}
    
    	printf("%d\n", count);
    }

这个函数中并不是给我们一个未知数，而是直接给我们一个常数100，可能有的小伙伴会认为它的时间复杂度就是O(100), 其实并不是这样的。大O的渐进表示法第一条上写道：1、用常数1取代运行时间中的所有加法常数， 因此func4函数的时间复杂度是O(1)哦！

同时我们也要知道时间复杂度O(1) 并不是说只能进行一次运算，而是能运行常数次。

> 实例4：计算strchr的时间复杂度？

const char* strchr(const char* str, int character);

首先我们要了解strchr的大致内容：

![fc2a6526459242519074c1bcb69f696c.png][]

根据最坏的运行结果，strchr的时间复杂度为O(N) (N为\*str的长度)

> 实例5：计算Bubblesort的时间复杂度？

void Bubb1eSort(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;
    	}
    }

我们先对冒泡排序的过程进行分析：

当end=n时： 第二层for循坏执行 N-1 次

当end=n-1时：第二层for循坏执行 N-2 次

当end=n-2时：第二层for循坏执行 N-3 次

当end=n-3时：第二层for循坏执行 N-4 次

——

当end=2时： 第二层for循坏执行 1次

总的执行次数就是 1+2+3+4+..+N=N\*(N-1)/2

因此Bubblesort的时间复杂度为 O(N^2)

这个实例间接表明：算时间复杂度不能只看是几层循环，而要看它的思想

> 实例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;
    }

计算二分查找的时间复杂度也是看它的最坏情况：

开始时要查找的范围是N，每次查找一次，范围就缩小一倍，即N/2/2/2/....(N>=0)

因此二分查找的时间复杂度是 O(log 2 N)

> 实例7：计算阶乘递归Fac的时间复杂度？

long long Fib(size_t N)
    {
    	if (N < 3)
    		return 1;
    	return Fib(N - 1) + Fib(N - 2);
    }

解释起来有点麻烦，不如直接看图：

![5f388725586c4c6a80028dba8917b7ef.png][]

## 空间复杂的概念 ##

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

### 空间复杂的的计算方法 ###

> 实例1：计算Bubblesort的空间复杂度？

在函数内就只定义了两个变量——end 和 i

虽然每经过一次循环end和i都会被销毁，但是当循环再次开始时，再次定义 end 和 i 它们还是使用原来那块空间，所以函数额外使用的空间数是2.

所以本题的空间复杂度为：O(1)

> 实例2：计算Fibonacci的空间复杂度？
> 
> 返回斐波那契数列的前n项

1ong 1ong * Fibonacci(size_t n)
    {
    	if (n == 0)
    		return NULL;
    
    	1ong 1ong * fibArray = (1ong 1ong*)ma11oc((n + 1) * sizeof(1ong 1ong));
    	fibArray[0] = 0;
    	fibArray[1] = 1;
    	for (inti = 2; i <= n; ++i)
    	{
    		fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    	}
    
    	return fibArray;
    }

很明显，空间复杂度是O(N), 因为开了一个n+1的数组

顺便计算它的时间复杂度：O(N) 函数内就只有一层for循环

> 实例3：计算阶乘递归Fac的空间复杂度？

1ong 1ong Fac(size_t N)
    {
    	if (N == 1)
    		return 1;
    
    	return Fac(N - 1) * N;
    }

每次递归都要建立栈帧,每个栈帧创建常数个变量，递归n次就建立了n个栈帧，因此空间复杂度是 O(N)

递归函数的空间复杂的与递归的深度有关

## 时间和空间复杂度的应用 ##

### 消失的数字 ###

原题链接：[力扣][Link 1]

![213d506fe154417995f661b92646049e.png][]

**思路：**

方法一：先对数组中的元素进行排序，需要用到qsort快排，时间复杂度为O(n\*log2N)

方法二：先求出前n项和sum=(1+n)\*n/2, 然后要求的数x=sum-(a\[0\]+a\[1\]+a\[2\]+...+a\[n-1\]) , 时间复杂度是O(N),空间复杂度是O(1)

方法三：创建长度n的数组，原数组中值是几就在第几个位置写一下这个值，然后遍历数组，找出没有值的那一项，时间复杂度是O(N),空间复杂度是O(N)

方法四：给一个值x=0，先让x与0~n进行异或，再让x与数组中的每一个值进行异或，最后x就是要求的数， 时间复杂度是O(N)

**使用方法四来解题：**

int missingNumber(int* nums, int numsSize)
    {
        int x=0;
        //跟[0,n]异或
        for(int i=1;i<=numsSize;i++)
        {
            x^=i;
        }
        //在跟数组中值异或
        for(int i=0;i<numsSize;i++)
        {
            x^=nums[i];
        }
        return x;
    }

### 轮转数组 ###

原题链接：[力扣][Link 2]

![d98794e03ee741039dc5a5e6fef7e34b.png][]

方法一：暴力求解，旋转k次 时间复杂度是O(N\*K),空间复杂度是O(1)

方法二：开辟额外空间 以空间换时间 时间复杂度是O(N),空间复杂度是O(N)

![2d1f28db54e94b15a64e28aa0b9a9b24.png][]

方法三：首先将前n-k个逆置，再将后k个逆置，最后整体逆置， 时间复杂度是O(N),空间复杂度是O(1)

![f97404bf9c5e480e819a392fc0bb26f2.png][]

**用方法三来解题：**

void reverse(int*nums,int left,int right)
    {
        while(left<right)
        {
            int tem=nums[left];
            nums[left]=nums[right];
            nums[right]=tem;
            ++left;
            --right;
        }
    } 
    
    void rotate(int*nums,int numsSize,int k)
    {
        if(k>=numsSize) k%=numsSize;
        //前n-k个数逆置
        reverse(nums,0,numsSize-k-1);
        //后k个逆置
        reverse(nums,numsSize-k,numsSize-1);
        //整体逆置
        reverse(nums,0,numsSize-1);
    }

全文结束就结束啦~~

![02659e14f70b4239adb39d3461b052b6.gif][]

[e07dc75556f94b459906f08587a2c895.png]: https://img-blog.csdnimg.cn/e07dc75556f94b459906f08587a2c895.png
[d21c72e695a24d34b4799b2aaefad898.png]: https://img-blog.csdnimg.cn/d21c72e695a24d34b4799b2aaefad898.png
[fc2a6526459242519074c1bcb69f696c.png]: https://img-blog.csdnimg.cn/fc2a6526459242519074c1bcb69f696c.png
[5f388725586c4c6a80028dba8917b7ef.png]: https://img-blog.csdnimg.cn/5f388725586c4c6a80028dba8917b7ef.png
[Link 1]: https://leetcode.cn/problems/missing-number-lcci/submissions/
[213d506fe154417995f661b92646049e.png]: https://img-blog.csdnimg.cn/213d506fe154417995f661b92646049e.png
[Link 2]: https://leetcode.cn/problems/rotate-array/
[d98794e03ee741039dc5a5e6fef7e34b.png]: https://img-blog.csdnimg.cn/d98794e03ee741039dc5a5e6fef7e34b.png
[2d1f28db54e94b15a64e28aa0b9a9b24.png]: https://img-blog.csdnimg.cn/2d1f28db54e94b15a64e28aa0b9a9b24.png
[f97404bf9c5e480e819a392fc0bb26f2.png]: https://img-blog.csdnimg.cn/f97404bf9c5e480e819a392fc0bb26f2.png
[02659e14f70b4239adb39d3461b052b6.gif]: https://img-blog.csdnimg.cn/02659e14f70b4239adb39d3461b052b6.gif