【数据结构】时间复杂度

• 🚩 WRITE IN FRONT 🚩   
• 🔎 介绍："謓泽"正在路上朝着"攻城狮"方向"前进四" 🔎
• 🏅 荣誉：2021|2022年度博客之星物联网与嵌入式开发TOP5|TOP4、2021|2022博客之星TOP100|TOP63、阿里云专家博主、掘金优秀创作者、全网粉丝量6w+、全网访问量100w+ 🏅
• 🆔 文章内容由 謓泽 原创 如需相关转载请提前告知博主 ⚠
• 📝 个人主页：謓泽的博客 📃
• 📣 专栏系列：数据结构_謓泽的博客 📃
• 🎁 点赞👍+ 收藏⭐️+ 留言📝​
• 📅 创作时间👉 挺久之前了，不记得了😶‍🌫️
• ✉️ 我们并非登上我们所选择的舞台，演出并非我们所选择的剧本 📩

💕 学习的重点

概述⇢在讲解数据结构之前、我们先来介绍下关于数据结构学习当中的重点目标知识点。

说明⇢数据结构的学习方面分为两个方面。

⒈各种数据结构的定义、特性、适用场景。掌握这些理论基础，你才能知道什么场景下应该

使用链表、红黑树、哈希表。

⒉其次能够使用一种语言熟练的实现这些数据结构。一般在项目开发当中，我们是不需要自己实现数据结构的、一般成熟的面向对象都有自己的数据结构库、如C++的STL(C++算法当中的库)，Java的集合类。但是造轮子是一个深度的学习过程，经过这样的学习，你对数据结构的理解就脱胎换骨了，能够更加高效的使用他们。其次技术进阶的一个必经之路就是学习开源的项目，很多的开源项目都用了很多的数据结构，数据结构不扎实的话就相当于技术进阶的拦路虎。

✨ who 时间「复杂度」

说明⇢算法效率分析分为两种。

⒈时间效率。

解释⇢时间效率被称之为是时间复杂度。时间复杂度主要衡量的是一个算法的运行速度。在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费多的时间，从理论来说，是不能算出来的，只有你把你的程序仿真机器跑起来的话，才能够被知道。但是我们需要每个算法都要进行上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度的这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。 

⒉空间效率。

解释⇢空间效率被称之为是空间复杂度。空间复杂度主要是衡量的是一个算法所需要的额外的空间，在计算机发展的早期时代，计算机的存储容量已经到达了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

⒊注意。

说明⇢实际当中我们最最关心得还是时间效率。

✨ 时间复杂度

✔重点再次强调下⇢算法中的基本操作的执行次数，为算法的时间复杂度。

🍊示例代码如下⇲

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void fun(N)
{
	int i = 0;
	int j = 0;
	int count = 0;//计算被执行多少次。
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < N; j++)
		{
			count++;
		}
	}
	printf("count1=%d\n", count);
	for (i = 0; i < 2 * N; i++)
	{
		count++;
	}
	printf("count2=%d\n", count-100);
	i = 10;
	while (i--)
	{
		count++;
	}
	printf("count3=%d\n", count-120);
}
int main(void)
{
#define N 10
	fun(N);
}

运行结果🖋

count1=100

count2=20

count3=10

📝说明⇢这里我们需要知道的是fun所执行的次数。

表达式－F(N) = N²+2*N+N

• N = 10 F(N) = 130 ⇿ O(N²)
• N = 100 F(N) = 10210 ⇿ O(2*N)
• N = 1000 F(N) = 1002010 ⇿ O(N)

📝说明⇢随着N的表达式越大、N²对结果的影响是最大的，在上述中分别是100、10000、1000000的。

😶‍🌫️注意⇢在上述的例题是只有一个未知数的，而时间复杂度不仅仅只有一个未知数，有些题目有两个甚至多个。

🎉 大O的渐进表示法

📝说明⇢这个大O的渐进表示法实际上就是一个估算。那么在上述的示例代码就会写成时间复杂度:O(N²) 在表达式当中不会去看后面的两项，因为对结果影响不大。类似于数学当中的极限。

🉑解释大O符号(Big O notation)⇢用于描述函数渐进的行为数字符号。

🎓总结⇢时间复杂度它是一个估算，是去看表达式当中影响值最大的那一项、也可以说是保留最高阶项。

🎉 推导大O阶的方法

⒈用常数1取代运行时间中的所有加法常数，即使这个常数再大，算法的时间复杂度还是O(1)

⒉修改后的运行次数函数当中，只保留最高阶项。

⒊如果最高阶项存在且不是1(常数)，则去除与这个项目相乘的常数。得到结果就是大O阶。注意⇢同等数量级可忽略!

• 以上三点请牢牢记住!
• 注：N相当于是算法当中执行次数。

💕 最优时间复杂度

第一个肯定是O(1)随着数量次数的增加，次数是不会改变的。如果一个算法是O(1)的话、那么它就是最🐂的，不可能有比O(1)更牛的算法了。

第二个其次就是O(logN)、像二分查找有序的它的时间复杂度就是O(logN)

说明⇢1*2*2*2...*2=N、2^X=N、X=log₂(底数)N(真数)。

loga(底数)b(真数)=X ⇿ a^x=b 「对数函数」 

举个例子吧，假设N=1000 那么logN=(1000=2^10) 这里就相当于你如果没有用二分查找那么你的时间复杂度相当于是O(N)、你用了二分查找法只是O(logN)

说明⇢这里如果N=1000、那么logN=10 从这里就可以看出O(logN)和O(1)是一个量级的。

注意⇢算法的复杂度计算，喜欢简写成为logN，因为很多地方不好写底数。

第三个是O(N)算是普遍来说最普通的时间复杂度了，也是我们实际情况遇到最多的。

第四个是O(N^2)这个就比较花费执行次数了。

第五个效率最低的就是O(N!)了。

💕 有些算法的时间不同情况

1. 最好的情况－任意输入规模的最小运行次数O(1)。(下界)  
2. 平均的情况－任意输入规模的期望运行次数O(N/2)。
3. 最坏的情况－任意输入规模的最大运行次数O(N)。(上界)

• 最好的情况－1次找到。
• 最坏的情况－N次找到。
• 平均的情况－N/2次找到。

📝说明⇢在实际的情况当中一般我们关注算法是最坏的运行情况，所以数组中搜索数据时间复杂度为O(N)

🧑‍💻 冒泡排序算法

📝说明⇢相信看过前面C语言部分的小伙伴，应该知道什么是冒泡排序，那么我们就来求下冒泡排序当中的时间复杂度是多少。

#pragma warning(disable:6031)
#pragma message("第xxx题→冒泡排序")
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void sort_jx(int arr1[],int sz)
{
	int i = 0;
	//1.确定总的排序次数
	//2.相邻之间的元素比较
	//3.确定比较次数,然后进行交换。
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz-1-i; j++)
		{
			if (arr1[j] < arr1[j + 1])
			{
				int temp = 0;
				temp = arr1[j];
				arr1[j] = arr1[j + 1];
				arr1[j + 1] = temp;
			}
		}
	}
}
void sort_sx(int arr2[],int sz)
{
	int i = 0;
	//1.确定总的排序次数
	//2.相邻之间的元素比较
	//3.确定比较次数,然后进行交换。
	for (i = 0; i < sz; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
			if (arr2[j] > arr2[j + 1])
			{
				int temp = 0;
				temp = arr2[j];
				arr2[j] = arr2[j + 1];
				arr2[j + 1] = temp;
			}
		}
	}
}
void traversal(int arr1[], int arr2[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr1[i]);
	}
	printf("\n");
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr2[i]);
	}
}
int main(void)
{
	int i = 0;
	int arr1[] = { 2,1,3,4,5,6,7,8,9,10 };
	int arr2[] = { 10,9,8,7,6,5,4,3,2,1 };
	int sz = sizeof(arr1) / sizeof(arr2[0]);
	sort_jx(arr1,sz);
	sort_sx(arr2,sz);
	traversal(arr1,arr2,sz);
	return 0;
}

第一趟冒泡：N

第二趟冒泡：N-1

第三趟冒泡：N-2

第N 趟冒泡：1

拓展知识点⇢在这里我们可以用等差数列的公式来计算－(首项+尾项)*项数/2⇿(N+1)*N/2

说明⇢时间复杂度:O(N²)

注意⇢不是说一层循环就是:O(N²)、两层循环就是:O(N²)、具体情况要根据题目去分析。