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

在这里插入图片描述

👦个人主页:@Weraphael
✍🏻作者简介:目前学习C++和算法ing
✈️专栏:【数据结构】
🐋 希望大家多多支持,咱一起进步!😁
如果文章对你有帮助的话
欢迎 评论💬 点赞👍🏻 收藏 📂 加关注


目录

  • 一、时间复杂度的概念
  • 二、时间复杂度的计算
      • 2.1 例题
      • 2.2 大O的渐进表示法
  • 三、常见时间复杂度计算举例
      • 3.1 实例1
      • 3.2 实例2
      • 3.3 实例3
      • 3.4 实例4
      • 3.5 实例5 --- 冒泡排序
      • 3.6 实例6 --- 二分查找
      • 3.7 实例7 --- 递归
      • 3.8 实例8 --- 斐波那契数列
  • 四、空间复杂度
  • 五、空间复杂度例题
      • 5.1 - 冒泡排序
      • 5.2 - 斐波那契
      • 5.3 - 递归
      • 5.4 斐波那契
  • 四、总结

一、时间复杂度的概念

  • 算法的时间复杂度是一个函数式,它定量描述了该算法的运行时间
  • 算法中的基本操作的执行次数,为算法的时间复杂度。即找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度

二、时间复杂度的计算

2.1 例题

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

【分析】
在这里插入图片描述

通过分析,不难可以写出时间复杂度的函数式:

在这里插入图片描述

当N = 10时,F(N) = 130
当N = 100时,F(N) = 10210
当N = 1000时,F(N) = 1002010

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

2.2 大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号

推导大O阶方法

  1. 用常数1取代运行时间中的所有加法常数,记作:O(1)
  2. 只保留最高阶项。假设一个函数式为F(N) = N2 + N,记作:O(N2)
  3. 如果最高阶项存在且不是1,则去除与这个项目相乘的常数。假设一个函数式为F(N) =2N,记作O(N)

总结:
大O的渐进表示法就是去掉了对结果影响不大的项,简洁明了的表示出了执行次数

另外有些算法的时间复杂度存在最好、平均和最坏情况

  • 最坏情况:任意输入规模的最大运行次数(上界)
  • 平均情况:任意输入规模的期望运行次数
  • 最好情况:任意输入规模的最小运行次数(下界)

例如:在一个长度为N数组中搜索一个数据x
最好情况:1次就能找到
平均情况:N / 2次找到
最坏情况:需要遍历数组,也就是N次
但在实际中,一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)

【解析2.1例题代码】

使用大O的渐进表示法,只保留最高阶项,所以,时间复杂度为O(N * N)

三、常见时间复杂度计算举例

3.1 实例1

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

【解析】

在这里插入图片描述

通过分析,不难可以写出时间复杂度的函数式:

在这里插入图片描述

只保留最高阶项以及如果最高阶项存在且不是1,则去除与这个项目相乘的常数。所以,这题的时间复杂度:O(N)

3.2 实例2

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)

3.3 实例3

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

【分析】

在这里插入图片描述

用常数1取代运行时间中的所有加法常数,所以此题的时间复杂度为O(1)

3.4 实例4

char* strchr(const char* str, char c)
{
	while (*str)
	{
		if (*str == c)
		{
			return str;
		}
		str++;
	}
}
//打印指定字字符后面的字符串(包括指定字符)
int main()
{

	char t;
	char a[] = "abcdef";
	scanf("%c",&t);
	char* res = strchr(a,t);
	printf("%s\n",res);
	return 0;
}

【分析】

代码逻辑相当于字符查找,运气最好执行1次,最坏N次,然而时间复杂度一般看最坏情况,时间复杂度为 O(N)

3.5 实例5 — 冒泡排序


void Sort(int arr[],int sz)
{
  
	for (int i = 0; i < sz-1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
     
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
	}

【分析】

  • 冒泡排序最好情况下:如果元素本来就有序,那么一趟冒泡排序就可以完成排序,也就是N - 1次,因此最好情况的时间复杂度为O(N)
  • 最差情况的时间复杂度:如果数据元素本来就是逆序的,第一个数需要比较N-1次,第二个数需要比较N-2次,第三个数需要比较N-3,…直到比较次数为1次时。这一套下来就是一个等差数列,总共就时N * (N - 1) / 2,因此最差的情况的时间复杂度为O(N2)
  • 综上,时间复杂度一般看最坏,时间复杂度为O(N2)

3.6 实例6 — 二分查找

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

【分析】

  • 二分查找最好的情况:一次二分就找到了,时间复杂度O(1)
  • 最坏的情况:一直二分,直到二分只剩下一个数,要么找到,要么找不到。假设N表示数组个数
    在这里插入图片描述
    所以,时间复杂度为O(log N)(注:在时间复杂度中,一般log的底数2可以省略不写)

3.7 实例7 — 递归

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

【分析】

在这里插入图片描述
通过上图计算分析发现,基本操作递归了N + 1次,+1影响不大,因此可以省略。所以时间复杂度为O(N)

3.8 实例8 — 斐波那契数列

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

【分析】

在这里插入图片描述
通过上图计算分析发现,其递归的次数是一个等比数列的和以及缺少部分的x,F(N) = 2N-1 + X,因此时间复杂度为O(2N

四、空间复杂度

  • 空间复杂度也是一个数学表达式,是对一个算法在运算过程中临时占用存储空间大小的量度。
  • 空间复杂度计算的是变量的个数,所以空间复杂度计算规则和时间复杂度类似,也使用大O渐进表示法。
  • 注意:函数运行时所需要的栈空间在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候申请的额外空间来确定

五、空间复杂度例题

5.1 - 冒泡排序

void BubbleSort(int* a, int n)
{
	for (int end = n; end > 0; end--)
	{
		int flag = 0;
		for (int i = 1; i < end; i++)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				flag = 1;
			}
		}
		if (flag == 0)
		{
			break;
		}
	}
}

解析:

在这里插入图片描述
在上图代码中,一共创建了3个变量,所以,空间复杂度为O(1)

5.2 - 斐波那契

typedef long long LL;
#include <stdlib.h>
LL* Fib(int n)
{
	if (n == 0)
		return 0;
	
	LL* FibArray = (LL*)malloc(sizeof(LL) * (n + 1));
	FibArray[0] = 0;
	FibArray[1] = 1;

	for (int i = 2; i <= n; i++)
	{
		FibArray[i] = FibArray[i - 1] + FibArray[i - 2];
	}
	return FibArray;
}

解析:

在这里插入图片描述
在上述代码中,向内存申请了n + 1,所以其空间复杂度为O(n)

5.3 - 递归

typedef long long LL;

LL Fac(int n)
{
	if (n == 0)
	{
		return 1;
	}

	return Fac(n - 1) * n;
}

解析:
在这里插入图片描述
如上述代码中,递归一共向内存申请了n - 1个空间,所以,空间复杂度为O(n)

5.4 斐波那契

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

解析:
在这里插入图片描述
以左半边为例,当n < 3时,递推停止,所以从Fib(0)开始回归。在回归的过程中,Fib(0)就会销毁,接着回归到Fib(2),然而Fib(2)又会调用Fib(1),销毁后又回到Fib(2)。所以,Fib(1)和Fib(2)相当于共用的是同一块空间。细推的话整个过程其实开辟了n + 1个空间。所以空间复杂度为O(n)

四、总结

常见复杂度所耗费的时间从小到大依次是:
O(1)
O(logN)
O(N)
O(NlogN)
O(N2)
O(N3)
O(2N)

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/6506.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

1662_MIT 6.828 JOS check_page_free_list实现分析以及boot_alloc问题修复

全部学习汇总&#xff1a; GreyZhang/g_unix: some basic learning about unix operating system. (github.com) 继续尝试完善分析JOS的代码中存储管理的部分。 上次看到了这里&#xff0c;本来想先去看看这两个函数实现。但是缺失了调用场景&#xff0c;感觉理解也不一定准确。…

对拍程序 并查集专题 (C++ | 洛谷 | acwing | 蓝桥)

文章目录【蓝桥杯专题】 &#xff08;C | 洛谷 | acwing | 蓝桥&#xff09;1249. 亲戚836. 合并集合837. 连通块中点的数量238. 银河英雄传说 【带权并查集】145. 超市 【并查集 贪心】4793. 危险程度 (连通块并查集 &#xff09;普通oi 读文件对拍程序【蓝桥杯专题】 &#…

树和二叉树相关的练习(选择题)

目录 一、二叉树 二、堆 三、遍历二叉树 一、二叉树 某二叉树共有 399 个结点&#xff0c;其中有 199 个度为 2 的结点&#xff0c;则该二叉树中的叶子结点数为&#xff08; &#xff09;。 A. 不存在这样的二叉树 B. 200 C. 198 D. 199 下列数据结构中&#xff0c;不适合…

C++ Primer Plus 学习笔记(八)——输入、输出和文件

1 流和缓冲区 C程序把输入和输出看作字节流。输入时&#xff0c;程序从输入流中抽取字节&#xff1b;输出时&#xff0c;程序将字节插入到输出流中。 缓冲区是用作中介的内存块&#xff0c;它是将信息从设备传输到程序或从程序传输给设备的临时存储工具&#xff0c;通过使用缓…

HTTP协议:当下最主流的应用层协议之一,你确定不了解一下吗?

一.HTTP协议的含义http是什么&#xff1f;超文本传输协议&#xff08;Hyper Text Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。‘超’可以理解为除了文本之外的图片&#xff0c;音频和视频&#xff0c;和一些其他…

STM32基于HAL工程FREERTOS读取DS18B20数据+串口输出

STM32基于HAL工程FREERTOS读取DS18B20数据串口输出✨申明&#xff1a;本文章仅发表在CSDN网站&#xff0c;任何其他网站&#xff0c;未注明来源&#xff0c;见此内容均为盗链和爬取&#xff0c;请多多尊重和支持原创!&#x1f341;对于文中所提供的相关资源链接将作不定期更换。…

无需公网IP,远程连接SQL Server数据库【内网穿透】

文章目录1.前言2.本地安装和设置SQL Server2.1 SQL Server下载2.2 SQL Server本地连接测试2.3 Cpolar内网穿透的下载和安装2.3 Cpolar内网穿透的注册3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置4.公网访问测试5.结语1.前言 数据库的重要性相信大家都有所了解&#xf…

现代前端开发者的自我迷失,你还会前端基础知识吗?

通常来说&#xff0c;我认为情况并不算糟糕&#xff0c;熟练的手可以几乎做到一切。然而&#xff0c;最近我注意到一些事情改变了我对这个行业的看法。似乎在这些无尽的趋势、范式和新奇玩意中&#xff0c;我们忘记了前端开发的支柱&#xff08;意思是忘记了基础知识&#xff0…

【python】GIL全局锁

一、原理&#xff1a; 全局解释器锁&#xff08;Global Interpreter Lock&#xff0c;GIL&#xff09;规定全局范围内任意时候一个进程里只能同时执行一个线程。每一个线程在执行时&#xff0c;都会锁住GIL&#xff0c;以阻止别的线程执行&#xff1b;执行一段时间后&#xff…

OBCP第四章 SQL调优-SQL执行性能监控

(g)v$sql_audit 全局 SQL 审计表 基于虚拟表__all_virtual_sql_audit的视图&#xff0c; 该虚拟表对应的数据存放在一个可配置的内存空间中 由于存放这些记录的内存是有限的&#xff0c;因此到达一定内存使用量&#xff0c;会触发淘汰 可以用来查看每次请求客户端来源&…

【操作系统复习】第3章 处理机调度与死锁 3

死锁&#xff08;Deadlock&#xff09;&#xff1a;指多个进程在运行过程中因争夺资源而造成的一种僵局&#xff0c;当进程处于这种僵持状态时&#xff0c;若无外力作用&#xff0c;这些进程都将永远不能再向前推进。 对资源不加限制地分配可能导致进程间由于竞争资源而相互制约…

JavaSE学习总结(十三)Set集合HashSet集合LinkedHashSet集合TreeSet集合比较器的使用利用Set集合实现去重

JavaSE学习总结&#xff08;十三&#xff09;Set集合/HashSet集合/LinkedHashSet集合/TreeSet集合/比较器的使用/利用Set集合实现去重 一、Set集合 Set集合是Collection集合的一个子接口&#xff0c;实际上Set就是Collection&#xff0c;只是行为略有不同&#xff1a; Set集…

VUE3项目实现动态路由demo

文章目录1、创建vue项目2、安装常用的依赖2.1 安装elementUI2.2 安装axios2.3 安装router2.4 安装vuex2.5 安装store2.6 安装mockjs3、编写登录页面以及逻辑4、编写首页以及逻辑5、配置router.js6、配置store.js7、配置menuUtils.js&#xff08;动态路由重点&#xff09;8、配置…

树的前序遍历与中序遍历构造二叉树和树的中序遍历与后序遍历构造二叉树

目录 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 二.树的中序遍历与后序遍历构造二叉树 1.题目描述 2.问题分析 3.代码实现 三.问题思考 一.树的前序遍历与中序遍历构造二叉树 1.题目描述 给定两个整数数组 preorder 和 inorder &#xf…

【机器学习】Logistic回归---学习笔记

Logistic回归学习笔记Logistic回归学习线路预备知识&#xff1a;建议先去B站学习一下信息量&#xff0c;熵&#xff0c;BL散度&#xff0c;交叉熵的概念。Logistic回归的函数模型损失最小化架构分类函数最大概率分类函数阈值分类函数Logistic回归的优化算法梯度下降随机梯度下降…

4.5--计算机网络之基础篇--2.网址到网页解析--(复习+深入)---好好沉淀,加油呀

1.浏览器做的第一步工作是解析 URL 对 URL 进行解析&#xff0c;从而生成发送给 Web 服务器的请求信息 URL? URL 实际上是请求服务器里的文件资源 当没有路径名时&#xff0c;就代表访问根目录下事先设置的默认文件&#xff0c;也就是 /index.html 或者 /default.html 这些文件…

计算机网络复习笔记(三)物理层

文章目录一物理层的基本概念四大特性&#xff1a;两种信号&#xff1a;调制和编码传输介质三大部分二物理层的基本通信技术四种信道复用技术数据的传输方式三OSI模型一物理层的基本概念 四大特性&#xff1a; 机械特性 接口是怎么样的 电气特性 用多少伏的电 功能特性 线路上…

linux基础之计算机基础

一、计算机基础 &#xff08;1) 计算机发展&#xff1a;电子管、晶体管、集成电路、大规模集成电路 &#xff08;2) 冯诺依曼体系&#xff1a;用二进制表示数据和指令&#xff1b; 存储程序控制&#xff0c;程序和数据预先存入存储器&#xff1b; 计算机系统5大部分&#xf…

Python 高级编程(文件操作)

文件&#xff1a;存储在某种长期存储设备上的数据&#xff01;&#xff01;包括&#xff08;硬板 u 盘 移动硬盘 光盘&#xff09; 计算机中临时的数据&#xff1a; 存储在内存中&#xff0c;一旦操作结束&#xff0c;内存中的空间就会被释放 文件&#xff08;特指普通文本&am…

R语言 4.2.2安装包下载及安装教程

[软件名称]:R语言 4.2.2 [软件大小]: 75.6 MB [安装环境]: Win11/Win10/Win7 [软件安装包下载]: https://pan.quark.cn/s/b6f604930d04 R语言软件的GUI界面比较的简陋,只有一个命令行窗口,且每次创建图片都会跳出一个新的窗口,比较的繁琐,我们可以安装RStudio,来更方便的操作R(…
最新文章