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

心已赠人 2023-10-14 15:39 64阅读 0赞

## ![e61b217d127b4255be216f0ceb7db8a7.png][] ##

## 算法的复杂度： ##

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

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

#### 算法的复杂度在当今的考核形式： ####

![b1ccf536ca654858a4afeb6ec0af7818.png][]

![3840283c67dc41bead1c79a2ce0ff036.png][]

**某学长** **CVTE** **面试：**

> 1. 怎么计算一个类到底实例化了多少对象？ 
> 
> 2. 如果还有一个派生类继承了这个类，那么如何计算这两个类，各自实例化了多少对象？ 
> 
> 3. 你了解联合体和结构体吗？ 
> 
> 4. 如何测试一个机器是大端还是小端？ 
> 
> 5. **你了解队列和栈吗？** 
> 
> 6. **怎么用两个栈实现一个队列。** 
> 
> 7. 你使用过模版吗？ 
> 
> 8. 写一个比较两个数大小的模板函数。 
> 
> 9. **你使用过容器吗？** 
> 
> 10. **判断两个链表是否相交。** 
> 
> 11. **Vector** **和数组的区别。** 
> 
> 12. 你在学校里做的最满意的一个项目是什么？简述一下这个项目。

**某学长腾讯的面试：**

> 1 、自我介绍 
> 
> 2 、 **学习** **STL** **具体是怎么开展的？** 
> 
> 3 、如果一款产品给你怎么检测内存泄露？ 
> 
> 4 、进程间通信方式，共享内存是怎么实现的，会出现什么问题，怎么解决？ 
> 
> 5 、 TCP 为什么是可靠的？可靠是怎么保证的？为什么要三次握手？为什么三次握手就可以可靠？ 
> 
> 6 、 Http 数据分包问题； 
> 
> 7 、 **Vector** **相关；** 
> 
> 8 、 **Hashmap** **相关；** 
> 
> 9 、 **红黑树的原理、时间复杂度等；** 
> 
> 10 、 Memcpy 和 memmove 的区别； 
> 
> 11 、客户端给服务器发送数据，意图发送 aaa ，然后再发 bbb ，但是可能会出现 aaabbb 这种情 
> 
> 况，如何处理？ 
> 
> 12 、游戏的邮件服务器中每天会有玩家频繁的创建邮件和删除邮件，海量数据、大小不一，会有 
> 
> 哪些场景，怎么存储，邮件是怎么到内存的？ 
> 
> 13 、写一道算法题

**某学姐百度的面试：**

> 1. **手写五道题，三道编程题** ，一道数据库，一道 linux 
> 
> 2. 数据库的题两问 
> 
> 3. **算法了解的如何，插入排序编程** 
> 
> 4. 说一下 IP,TCP,ARP 
> 
> 5. 内核是什么 
> 
> 比特科技 6.IP 层主要功能 
> 
> 7. **map** **和** **set** **底层** 
> 
> 8.bootstrap 的用法 ,html,html 的全称 
> 
> 9. 你觉得框架和库有啥区别 
> 
> 10. 代码优化 
> 
> 11. **哈希表** 
> 
> 12.shell 脚本 
> 
> 13. **快速排序思想** 
> 
> 14. **递归是什么** 
> 
> 15. 分治是什么，与递归区别是什么 
> 
> 16.web 平台是怎么做的 
> 
> 17.linux 命令 
> 
> 18. 了解些什么前沿的技术，英语怎么样，了解过什么英语的文献

#### 总结： ####

可以看出，现在 **公司对学生代码能力的要求是越来越高了，大厂笔试中几乎全是算法题而且难度**

**大，中小长的笔试中才会有算法题** 。算法不仅笔试中考察，面试中面试官基本都会让现场写代

码。而算法能力短期内无法快速提高了，至少需要持续半年以上算法训练积累，否则真正校招时

笔试会很艰难，因此算法要早早准备。

## 时间复杂度 ##

### **时间复杂度的概念：** ###

时间复杂度的定义：在计算机科学中， **算法的时间复杂度是一个函数** ，它定量描述了该算法的运行时间。一个算法所花费的时间与其中语句的执行次数成正比例，**算法中的基本操作的执行次数，为算法**  **的时间复杂度。**

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

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

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

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

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

### 算法复杂度记录情形： ###

> 另外有些算法的时间复杂度存在最好、平均和最坏情况： 
> 
> 最坏情况：任意输入规模的最大运行次数 ( 上界 ) 
> 
> 平均情况：任意输入规模的期望运行次数 
> 
> 最好情况：任意输入规模的最小运行次数 ( 下界 ) 
> 
> 例如：在一个长度为 N 数组中搜索一个数据 x 
> 
> 最好情况： 1 次找到 
> 
> 最坏情况： N 次找到 
> 
> 平均情况： N/2 次找到 
> 
> **在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为** **O(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 k = 0; k < 2 * N ; ++ k)
    {
     ++count;
    }
    int M = 10;
    while (M--)
    {
     ++count;
    }
    printf("%d\n", count);
    }

此程序中Func1中++count计算：**F(N) = N^2+2\*N+10;**

时间复杂度为：**O(N^2)**

#### 计算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);
    }

这段代码关键循环语句执行了 M+N 次，时间复杂度为：**O(M+N)**

#### 计算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);
    }

这段代码关键循环语句执行了 N+N 次，处理掉常数后时间复杂度为：**O(N)**

#### 计算Func4的时间复杂度？  ####

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

这段代码关键循环语句执行了 100次，所有的常数在大O表达式中都为1，

经过处理时间复杂度为：**O(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;
     }
    }

根据算法复杂度记录情形可知：执行次数为 (n-1)+(n-2)+(n-3)......+2+1=n\*n/2（等差数列求和），冒泡排序的时间复杂度为 **O(N^2)**

#### 计算BinarySearch的时间复杂度？    ####

int BinarySearch(int* a, int n, int x)
    {
     assert(a);
     int begin = 0;
     int end = n-1;
     // [begin, end]：begin和end是左闭右闭区间，因此有=号
     while (begin <= end)
     {
     int mid = begin + ((end-begin)>>1);
     if (a[mid] < x)
     begin = mid+1;
     else if (a[mid] > x)
     end = mid-1;
     else
     return mid;
     }
     return -1;
    }

计算可得到2 ^ x = N,通过数学运算知x= log N,时间复杂度为**O(logN)**,默认情况log的下标为2。

####  计算阶乘递归Fac的时间复杂度？ ####

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

时间复杂度为**O(N)**

#### 计算斐波那契递归Fib的时间复杂度？  ####

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

时间复杂度为**O(2^N)**

### **经典题型：消失的数字** ###

![a7d97056d2674740b2cdfb1dd5df3f06.png][]

#### 思路一： ####

排序+遍历（一个数 != 下一个数，这个消失的数就是要找的数）

时间复杂度：**O(logN\*N)**

#### 思路二： ####

将0--n的数全部加起来，然后减去数组中的值，最后得到的结果就是消失的数

时间复杂度：**O(N)**

int missNumber(int* nums, int numsSize)
    {
    	int N = numsSize;
    	int ret = N * (N + 1) / 2;
    	for (int i = 0; i < N; i++)
    	{
    		ret -= nums[i];
    	}
    	return ret;
    }

#### 思路三： ####

单身狗问题解法：异或“ ^ ”

时间复杂度：**O(N)**

解法：定义一个数tmp为0，与0--n的数进行异或，然后与题所给的数组进行再次异或，

得出消失的数；

基础：a^a=0;a^b^a=b;

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

## 空间复杂度 ##

### 概念： ###

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

空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，  **也使用大O渐进表示法**  。

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

#### 计算BubbleSort的空间复杂度？  ####

空间复杂度计算额外临时创建的变量，在这有size\_t end，size\_t i，int exchange = 0;三个，又因为是常量，所以空间复杂度： **O(1)**

#### 计算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)**

#### 计算阶乘递归Fac的空间复杂度？ ####

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

这里的Fac()函数递归调用N次Fac(),每次都创建一次临时空间，所以空间复杂度：**O(N)**

####  计算斐波那契递归Fib的kj复杂度？  ####

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

![9e6b0130db9d4294b1807ec6ab98cc27.png][]

通过与可以看出Fib()不断的调用，但是通过函数栈帧可以知道：

时间积累一去不复返；

空间可以重复利用；

这样就可以知道在创建Fib(2)后运行结束，会将Fib(2)销毁,然后才去执行Fib(1),这样就实现了空间上的重复利用，所以这里的空间复杂度：**O(N)**

##### **小知识：** #####

![e8cf03e39dee4e6fb798b7a060b22ee8.png][]![a0bb742556bd44a4a807a1cc01a6e553.png][]

通过左图可知，递归次数过多，会将堆栈爆满，造成溢出；

通过右图可知，函数调用后会将创建的内存销毁，其他的函数可以在这块空间上再创建，继续在这块空间上创建的主要因数是**类型。**

![71806368eab94666b678987fc5064285.png][]

![12b97de8e1b54c5ebf45cf71dc11d1ab.png][]

## 练习： ##

旋转数字(考虑时间复杂度和空间复杂度)

给定一个整数数组 `nums`，将数组中的元素向右轮转 `k`个位置，其中 `k`是非负数。

### 思路一： ###

如图：

![7466028f3bb94a889ce6a9efe6c6a58f.png][]

void rotate(int* nums, int numsSize, int k)
    {
    	int* tmp = (int*)malloc(sizeof(int) * numsSize);
    	k = numsSize % k;
    	
    	memcpy(tmp, nums + numsSize - k, sizeof(int) * k);
    	memcpy(tmp+k, nums, sizeof(int) * (numsSize - k));
    	memcpy(nums, tmp , sizeof(int) * numsSize);
    }

### 思路二： ###

创建reverse()函数传入三个值分别为数组地址，从第几个数组元素开始，结束元素位置；

在reverse（）函数中实现颠倒，swap()函数实现交换。

先将数组分为两部分0--(k-1)和k--(sz-1),然后分别旋转；

//交换位置
    void swap(int* a, int* b) {
        int t = *a;
        *a = *b, *b = t;
    }
    //实现颠倒
    void reverse(int* nums, int start, int end) {
        while (start < end) {
            swap(&nums[start], &nums[end]);
            start += 1;
            end -= 1;
        }
    }
    //起始位置
    void rotate(int* nums, int numsSize, int k)
    {
        int sz = numsSize;
        int i = 0;
        int j = 0;
        int tmp = 0;
        k = k % sz;
        reverse(nums,0,sz-1);
        reverse(nums,0,k-1);
        reverse(nums,k,sz-1);
    
    }

自此数据结构算法复杂度学习结束！

## 重要的事情说三遍： ##

**记得三连！ 记得三连！ 记得三连！**

[e61b217d127b4255be216f0ceb7db8a7.png]: https://img-blog.csdnimg.cn/e61b217d127b4255be216f0ceb7db8a7.png
[b1ccf536ca654858a4afeb6ec0af7818.png]: https://img-blog.csdnimg.cn/b1ccf536ca654858a4afeb6ec0af7818.png
[3840283c67dc41bead1c79a2ce0ff036.png]: https://img-blog.csdnimg.cn/3840283c67dc41bead1c79a2ce0ff036.png
[a7d97056d2674740b2cdfb1dd5df3f06.png]: https://img-blog.csdnimg.cn/a7d97056d2674740b2cdfb1dd5df3f06.png
[9e6b0130db9d4294b1807ec6ab98cc27.png]: https://img-blog.csdnimg.cn/9e6b0130db9d4294b1807ec6ab98cc27.png
[e8cf03e39dee4e6fb798b7a060b22ee8.png]: https://img-blog.csdnimg.cn/e8cf03e39dee4e6fb798b7a060b22ee8.png
[a0bb742556bd44a4a807a1cc01a6e553.png]: https://img-blog.csdnimg.cn/a0bb742556bd44a4a807a1cc01a6e553.png
[71806368eab94666b678987fc5064285.png]: https://img-blog.csdnimg.cn/71806368eab94666b678987fc5064285.png
[12b97de8e1b54c5ebf45cf71dc11d1ab.png]: https://img-blog.csdnimg.cn/12b97de8e1b54c5ebf45cf71dc11d1ab.png
[7466028f3bb94a889ce6a9efe6c6a58f.png]: https://img-blog.csdnimg.cn/7466028f3bb94a889ce6a9efe6c6a58f.png