算法的时间复杂度和空间复杂度

野性酷女 2023-10-10 23:39 54阅读 0赞

**目录**

本章重点

一 时间复杂度

2.1 时间复杂度的概念

2.2 大O的渐进表示法

2.3 常见的时间复杂度的计算

二 空间复杂度

三 常见复杂度对比

四 复杂度的oj练习

4.1 消失的数字

4.2 旋转数字

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

每一天都是人生限定，每一天都值得100%努力

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

## 本章重点 ##

（1）算法效率（2）时间复杂度（3）空间复杂度（4）常见的时间复杂度以及复杂度oj练习

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

衡量一个算法的好坏，是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法运行的快慢，空间复杂度主要衡量一个算法运行所需要的额外空间。

## 一 时间复杂度 ##

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

算法的时间复杂度是一个函数（指的是数学函数），算法中的基本操作的执行次数，为算法的时间复杂度。

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

> （1）时间复杂度表达式为：F（N） = N\*N+2 \* N + 10  
> （2）大O渐进表示法：O(N^2)
> 
> 这个函数的基本操作次数是：F（N） = N\*N+2 \* N + 10，随着N的增大，后两项对整个影响的结果变可以忽略不计小。当N无限大的时候，后两项对结果的影响

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

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

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

**推导大** **O** **阶方法：**

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

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

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

4.另外有些算法的时间复杂度存在最好、平均和最坏情况： 最坏情况：任意输入规模的最大运行次数(上界) ；平均情况：任意输入规模的期望运行次数 ；最好情况：任意输入规模的最小运行次数(下界)；在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

### 2.3 常见的时间复杂度的计算 ###

**代码一：**

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

**时间复杂度为**O（1）【因为大O的渐进表示法的第一条用常数1取代运行时间中的所有加法**常数**。】（我们可以看到执行次数为100）（所以，看到大O的渐进表示法，并不是让我们只能执行一次）（常数都是1）

**代码二：**

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

**时间复杂度为**O(N)\[大O的渐进表示法，第三条：如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。【实际的执行次数是：2\*N+10】

**代码三：**

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

**时间复杂度为**O(N+M);如果给出N远大于M，就可以写成O(N)；如果给出N和M差不多就可以写成O(N)或者O(M)；该代码什么都没有给，所以就是O(M+N)；

**代码4**

const char* strchr(const char* str, int character)
    {
    	while (*str)
    	{
    		if (*str == character)
    			return str;
    		else
    			++str;
    	}
    	return NULL;
    }

**时间复杂度为**O(N)；因为不确定什么时候被找到，第四条：在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

> 关于时间复杂度，我们要准确分析时间复杂度，一定要去看思想，不能仅仅去看程序是几层循环，主要是要看代码的思想。比如：冒泡排序（O(N^2)），就是N-1,N-2,N-3……2,1,是一个等差数列（N-1+1）(N-1)/2=N(N-1)【这是最差情况】，N-1【最好的情况】。

> 二分查找的时间复杂度：O(㏒₂N )【最好的情况：O(1)一次找到； 最差的情况(找不到的情况）：O(log2 N ) （1\*2\*2\*2…2)^X(次）= N(从找不到的时候，向前思想】
> 
> 时间复杂度，会把O（㏒₂N）**简写**成O(logN).有些书籍也会写成O(lgN)（这个是不正规的）

代码5

long long Fac(size_t N)
    {//阶乘
    	if (0 == N)
    		return 1;
    
    	return Fac(N - 1) * N;
    }

**时间复杂度为**O(N)，；实际上是N+1

**代码6**

long long Fac(size_t N)
    {
    	if (0 == N)
    		return 1;
    	for (size_t i = 0; i < N; ++i)
    	{
    		printf("%d", i);
    	}
    	printf("\n");
    
    	return Fac(N - 1) * N;
    }

**时间复杂度为**O(N^2)，；实际上是(N-1)+（n-2）+……+1+0

> 递归算法的时间复杂度：1、每次函数调用如果是是O(1)，那么就看他的递归次数（递归次数是多少，时间复杂度就是多少)（代码5）
> 
> 2、如果不是O(1)，那么就看他的递归调用次数的累加（每次递归，函数调用的累加）（代码6）

**代码7**

long long Fib(size_t N)
    {
     if(N < 3)
     return 1;
     
     return Fib(N-1) + Fib(N-2);
    }
    //斐波那契数列
    //符合递归算法的第一种

**时间复杂度为**O(2^N)，第一层调用一次，第二层 调用2次，第三层调用4次 ，一直到Fib（3）分成Fib（2）+Fib（1），那就是N-1层（假设每一层都是满的，起始并不是每一层都是满的），那最后一层就是2^(N-1)，然后就是等比数列相加，就是(2^n-1)-1,

## 二 空间复杂度 ##

空间复杂度 也是一个数学表达式，是对一个算法在运行过程中 临时占用存储空间 大小的量度 。

空间复杂度算的是 变量的个数, 空间复杂度计算规则基本跟实践复杂度类似，也使用**大** **O** **渐进表示法** 。 注意：**函数运行时所需要的栈空间** **(** **存储参数、局部变量、一些寄存器信息等** **)** **在编译期间已经确定好了，因** **此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定**

代码一：

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(1)，临时占用储存空间的变量有i、exchange、end，一共三个。

代码2

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

**空间复杂度为**O(N)，临时占用储存空间有指针开辟的空间n+1个,指针fibArray,i;一共n+3个

代码3

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

**空间复杂度为**O(N)， 递归调用了N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间。空间复杂度为 O(N)

代码4

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

**时间复杂度为O(2^N),空间复杂度为**O(N)，会误认为空间复杂度也是O(2^N),但是递归的调用的函数，调用完之后就销毁了，把空间还给系统了，下次调用的时候，再次开辟，空间又被使用，空间是可以重复利用。所以仍然是那一份空间。（局部变量存在栈上面，函数结束，局部变量也就销毁了）

> 知识点：时间一去不复返，是累积的，空间回收以后，可以重复利用。

## 三 常见复杂度对比 ##

一些常见的复杂度

![b4fa9031965c4a0c9673bc33a1d979ec.png][]

## 四 复杂度的oj练习 ##

### 4.1 消失的数字 ###

数组`nums`包含从`0`到`n`的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。(时间复杂度为O(N)

输入：\[3,0,1\]输出：2；

**思路一:**先排序，然后进行遍历（冒泡O(N^2），看是否是前一个数字+1得到的值（但是时间复杂度不符合题意）

**思路二:**映射方式（首先定义一个数组，里面的值全部赋值成-1，然后输入的数组，每一个值是多少，就作为下标对应的位置写多少）（时间复杂度为：O(N)）

**思路三:**异或（用一个val和0-N的数字异或，再和数据中的数字异或，最后cal中得知就是缺失的值）（O(N)）

**思路三:**等差数列(O(N))

**代码1展示：**（思路三）函数接口型

int missingNumber(int* nums, int numsSize){
        int x = 0;
        for (int i = 0; i < numsSize; ++i)
        {
            x ^= nums[i];
        }
        for (int i = 0; i < numsSize + 1; ++i)
        {
            x ^= i;
        }
        return x;
    
    }

### 4.2 旋转数字 ###

给定一个整数数组 `nums`，将数组中的元素向右轮转 `k`个位置，其中 `k`是非负数。输入: nums = \[1,2,3,4,5,6,7\], k = 3输出: \[5,6,7,1,2,3,4\]解释:向右轮转 1 步: \[7,1,2,3,4,5,6\]向右轮转 2 步: \[6,7,1,2,3,4,5\]向右轮转 3 步: \[5,6,7,1,2,3,4\]

**思路一:**右旋K次（每次右旋一次）【时间复杂度为O(N\*K)；空间复杂度为O(1)】（时间复杂度的k最大为N-1），最坏的结果为O(N^2)）

**思路二:**开设一个新的数组，把后k个放到新数组的前面，前面的依次放到后面【时间复杂度O(N),空间复杂度O(N)】 (这种方法比第一种，就是时间换取空间的算法）

**思路三:**三趟逆置【时间复杂度为O(N)，空间复杂度为O(1)】

(思路一和思路三在C语言进阶栏目-C进阶习题里面有详细说明 [http://t.csdn.cn/sFLCM][http_t.csdn.cn_sFLCM]）

思路三：（函数接口型）

void reverse(int* arr,int left, int right)
    {
        while (left < right)
        {
            int tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            ++left;
            --right;
        }
    }
    void rotate(int* nums, int numsSize, int k){
        int m = k % numsSize;
        reverse(nums, 0, numsSize - m - 1);
        reverse(nums, numsSize - m, numsSize - 1);
        reverse(nums, 0, numsSize -1);
    }

[b4fa9031965c4a0c9673bc33a1d979ec.png]: https://img-blog.csdnimg.cn/b4fa9031965c4a0c9673bc33a1d979ec.png
[http_t.csdn.cn_sFLCM]: http://t.csdn.cn/sFLCM