【数据结构】时间复杂度

淡淡的烟草味﹌ 2024-04-26 11:08 92阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏：[初阶数据结构][Link 1]  
> ?️博客主页：[睿睿的博客主页][Link 2]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言：
 *  1. 算法效率
 *   *  1.1 如何衡量一个算法的好坏
     *  1.2算法的复杂度
 *  2.时间复杂度
 *   *  2.1 时间复杂度的概念
     *  2.2 大O的渐进表示法
     *  2.3常见时间复杂度计算举例
     *   *  实列1：
         *  实列2：
         *  实列3：
         *  实列4：
         *  实列5：
         *  实列6：
         *  实列7：
         *  实列8：
 *  总结：

## 前言： ##

从今天开始我们将进入一个全新的环节：数据结构的学习！学习数据结构，首先就要学习算法的效率。下面我就带大家先来了解一下时间复杂度这个概念！

## 1. 算法效率 ##

### 1.1 如何衡量一个算法的好坏 ###

如何衡量一个算法的好坏呢？比如对于以下斐波那契数列

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

斐波那契数列的递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？

### 1.2算法的复杂度 ###

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从**时间和空间**两个维度来衡量的，即**时间复杂度**和**空间复杂度**。  
 时间复杂度主要衡量一个**算法的运行快慢**，而空间复杂度主要衡量一个**算法运行所需要的额外空间**。  
 经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。**所以我们如今已经不需要再特别关注一个算法的空间复杂度**。

## 2.时间复杂度 ##

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

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

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

![在这里插入图片描述][974379b531d3499d9bb41a257dc02958.png]  
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要**大概执行次数**，那么这  
里我们使用**大O的渐进表示法**

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

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

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

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

上面的栗子在使用大O的渐进表示法以后，Func1的时间复杂度为O(N^2)

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

另外有些算法的时间复杂度存在最好、平均和最坏情况：  
例如：在一个长度为N数组中搜索一个数据x  
最好情况：1次找到  
最坏情况：N次找到  
平均情况：N/2次找到  
在实际中一般情况关注的是算法的**最坏运行情况**，所以数组中搜索数据时间复杂度为O(N)

### 2.3常见时间复杂度计算举例 ###

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

**时间复杂度为O(N)**  
经过计算发现运算最坏情况次数为：2N(M为常数，不影响结果）

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

**时间复杂度为O(M)(M远大于N的时候）  
     或O(N)(N远大于M的时候)**  
经过计算发现运算最坏情况次数为：N+M

#### 实列3： ####

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

**时间复杂度为：O（1）**  
只要是常数，时间复杂度都为O（1）

#### 实列4： ####

// 计算strchr的时间复杂度？
    const char * strchr ( const char * str, int character )

**时间复杂度为O(N)**  
通过解析内部函数我们可以发现，要找到字符串中的字符，最坏情况需要n（字符串长度）次。

![在这里插入图片描述][2aa7af3295b84691bab2081a521b758a.png]

#### 实列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)**  
最好的情况是数组已经排好序，只用遍历一遍，O(N)，  
最坏的情况是数组没有排序，每一次都需要交换位置，O(N^2)

#### 实列6： ####

// 计算BinarySearch的时间复杂度？
    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);
    		if (a[mid] < x)
    			begin = mid + 1;
    		else if (a[mid] > x)
    			end = mid;
    		else
    			return mid;
    	}
    	return -1;
    }

**时间复杂度为：O（logN）**  
这是一个典型的二分查找,通过计算我们可以得出最坏情况需要查找log2(n)次  
![在这里插入图片描述][c679ab0cc20e449fbb793434850f3865.png]

#### 实列7： ####

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

**时间复杂度为O(N)**  
图解如下：  
![在这里插入图片描述][e4aa3d9a1d3142bcb039b4209b575e52.png]

#### 实列8： ####

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

**时间复杂度为O(2^N)**  
图解如下：通过等比数列求和去掉常数，得到时间复杂度  
![在这里插入图片描述][13471c26da194a0cb95271d6039f8c7e.png]

## 总结： ##

这就是时间复杂度的基本介绍！更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [c语言学习][c]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 1]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/bfc3f40c49c24ac786fa1dd3b4e26137.gif
[Link 1]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Link 2]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2be5a56315dd46d39b12f4ce82bed122.gif
[974379b531d3499d9bb41a257dc02958.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ef3b1b335c9f4d8fae26a7eb4c5be3b6.png
[2aa7af3295b84691bab2081a521b758a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/8b4b6ced2e8940bba774bdc71f5b04a9.png
[c679ab0cc20e449fbb793434850f3865.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/67311ee9da4a4a8dba01f7cfd10fd715.png
[e4aa3d9a1d3142bcb039b4209b575e52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/35c2c4af5f264a7ebd294bdde0563803.png
[13471c26da194a0cb95271d6039f8c7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b67f803df3c440148b2e59dbd18c0e1f.png
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[c]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/27ec8f191def4f4988364b842ea2a4bf.gif