【海贼王的数据航海：利用数据结构成为数据海洋的霸主】时间复杂度 | 空间复杂度

目录

1 -> 算法效率

1.1 -> 如何衡量一个算法的好坏？

1.2 -> 算法的复杂度

2 -> 时间复杂度

2.1 -> 时间复杂度的概念

2.2 -> 大O的渐进表示法

2.3 -> 常见时间复杂度计算

3 -> 空间复杂度

4 -> 常见复杂度对比

1 -> 算法效率

1.1 -> 如何衡量一个算法的好坏？

对于以下斐波那契数列：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

long long fib(int N)
{
	if (N < 3)
		return 1;

	return fib(N - 1) + fib(N - 2);
}

int main()
{

	

	return 0;
}

用递归实现斐波那契数列，看上去代码十分简洁，但简洁一定就是好算法吗？如何衡量一个算法的好坏？

1.2 -> 算法的复杂度

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

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

2 -> 时间复杂度

2.1 -> 时间复杂度的概念

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

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

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
using namespace std;

// 请计算一下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;

	cout << count << endl;
}

int main()
{


	return 0;
}

Func1执行的基本操作数：

F(N) = N^{2} + 2N + 10

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

使用大O的渐进表示法后，Func1的时间复杂度为：

O(N^{2})

-> N = 10 F(N) = 100

-> N = 100 F(N) = 10000
-> N = 1000 F(N) = 1000000

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

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

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

例如：在一个长度为N的数组中搜索一个数据x

  • 最好情况：1次找到
  • 平均情况：N / 2次找到
  • 最坏情况：N次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中的搜索数据时间复杂度为：

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;

	cout << count << endl;
}

实例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;

	cout << count << endl;
}

实例3：

// 计算Func4的时间复杂度？
void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
		++count;

	cout << count << endl;
}

实例4：

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

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

实例6：

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

实例7：

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

	return Fac(N - 1) * N;
}

实例8：

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

	return fib(N - 1) + fib(N - 2);
}

答案及分析：

1. 实例1基本操作执行了2N+10次，通过推导大O阶方法知道，时间复杂度为 O(N)
2. 实例2基本操作执行了M+N次，有两个未知数M和N，时间复杂度为 O(N+M)
3. 实例3基本操作执行了10次，通过推导大O阶方法，时间复杂度为 O(1)
4. 实例4基本操作执行最好1次，最坏N次，时间复杂度一般看最坏，时间复杂度为 O(N)
5. 实例5基本操作执行最好N次，最坏执行了(N*(N+1)/2次，通过推导大O阶方法+时间复杂度一般看最坏，时间复杂度为 O(N^2)
6. 实例6基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN) ps：logN在算法分析中表示是底数为2，对数为N。有些地方会写成lgN。
7. 实例7通过计算分析发现基本操作递归了N次，时间复杂度为O(N)。
8. 实例8通过计算分析发现基本操作递归了2^N次，时间复杂度为O(2^N)。

3 -> 空间复杂度

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

空间复杂度不是程序占用了多少byte的空间，因为意义不大，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本与时间复杂度类似，也是使用大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;
	}
}

实例2：

// 计算fib的空间复杂度？
// 返回斐波那契数列的前n项
long long* fib(size_t n)
{
	if (n == 0)
		return NULL;

	long long* arr = (long long*)malloc((n + 1) * sizeof(long long));
	arr[0] = 0;
	arr[1] = 1;
	for (int i = 2; i <= n; ++i)
		arr[i] = arr[i - 1] + arr[i - 2];

	return arr;
}

实例3：

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

	return Fac(N - 1) * N;
}

答案及分析：

1. 实例1使用了常数个额外空间，所以空间复杂度为 O(1)
2. 实例2动态开辟了N个空间，空间复杂度为 O(N)
3. 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

4 -> 常见复杂度对比

一般算法的常见复杂度：

5201314O(1)常数阶
3n + 4O(n)线性阶
3n ^ 2 + 4n + 5O(n ^ 2)平方阶
3log(2)n + 4O(logn)对数阶
2n + 3nlog(2)n + 4O(nlogn)nlogn阶
n ^ 3 + n ^ 2 + 3n + 4O(n ^ 3)立方阶
2 ^ nO(2 ^ n)指数阶

感谢大佬们支持！！！

互三啦！！！

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

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

相关文章

第2部分 基础篇 第2章 隐私计算技术简介(1)

第2部分 基础篇 第2章 隐私计算技术简介(1)

2.6.1. 隐私计算技术解决什么问题&#xff1f; 本聪老师&#xff1a;关于隐私计算&#xff0c;我想先问大家一个问题&#xff1a;隐私计算技术能够解决什么问题&#xff1f; 小明&#xff1a;是不是应该是保护用户的隐私。 本聪老师&#xff1a;可以这么说&#xff0c;但是怎…
阅读更多...
一 些有代表性的相位解包裹算法

一 些有代表性的相位解包裹算法

Itoh首先给出了传统解包裹算法的数学描述!。传统的相位解包裹操作是通过对空间相邻点相位值的比较来完成的。根据抽样定理&#xff0c;如果相邻采样点的相位差不超过z&#xff0c;则对应的相位解包裹处理是非常简单的&#xff0c;理论上以某点为起始点沿某一路径对包裹相位的差…
阅读更多...
如何使用Docker部署MongoDB并结合内网穿透实现远程访问本地数据库

如何使用Docker部署MongoDB并结合内网穿透实现远程访问本地数据库

文章目录 前言1. 安装Docker2. 使用Docker拉取MongoDB镜像3. 创建并启动MongoDB容器4. 本地连接测试5. 公网远程访问本地MongoDB容器5.1 内网穿透工具安装5.2 创建远程连接公网地址5.3 使用固定TCP地址远程访问 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 …
阅读更多...
机器学习第二十八周周报 PINNs2

机器学习第二十八周周报 PINNs2

文章目录 week28 PINNs2摘要Abstract一、Lipschitz条件二、文献阅读1. 题目数据驱动的偏微分方程2. 连续时间模型3. 离散时间模型4.结论 三、CLSTM1. 任务要求2. 实验结果3. 实验代码3.1模型构建3.2训练过程代码 小结参考文献 week28 PINNs2 摘要 本文主要讨论PINN。本文简要…
阅读更多...
如何利用内网穿透工具在企业微信开发者中心实现本地接口服务回调

如何利用内网穿透工具在企业微信开发者中心实现本地接口服务回调

文章目录 1. Windows安装Cpolar2. 创建Cpolar域名3. 创建企业微信应用4. 定义回调本地接口5. 回调和可信域名接口校验6. 设置固定Cpolar域名7. 使用固定域名校验 企业微信开发者在应用的开发测试阶段&#xff0c;应用服务通常是部署在开发环境&#xff0c;在有数据回调的开发场…
阅读更多...
猫头虎分享已解决Bug || Web服务故障：WebServiceUnavailable, HTTPServerError

猫头虎分享已解决Bug || Web服务故障：WebServiceUnavailable, HTTPServerError

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
跑步也要飙起来：南卡、韶音、墨觉骨传导耳机大比拼

跑步也要飙起来：南卡、韶音、墨觉骨传导耳机大比拼

作为一个热衷于运动同时又不能离开音乐的人&#xff0c;我总是在寻找一款既能让我自由奔跑&#xff0c;又能享受到美妙音乐的耳机。记得买耳机前&#xff0c;朋友都说骨传导耳机就像个小喇叭&#xff0c;漏音厉害&#xff0c;我却不这么认为。对我来说&#xff0c;骨传导耳机不…
阅读更多...
Pormise---如何解决javascript中回调的信任问题？【详解】

Pormise---如何解决javascript中回调的信任问题？【详解】

如果阅读有疑问的话&#xff0c;欢迎评论或私信&#xff01;&#xff01; 本人会很热心的阐述自己的想法&#xff01;谢谢&#xff01;&#xff01;&#xff01; 文章目录 回调中的信任问题回调给我们带来的烦恼&#xff1f;调用过早调用过晚调用的次数太少或太多调用回调时未能…
阅读更多...
【Django】Django自定义后台表单——对一个关联外键对象同时添加多个内容

【Django】Django自定义后台表单——对一个关联外键对象同时添加多个内容

以官方文档为例&#xff1a; 一个投票问题包含多个选项&#xff0c;基本的表单设计只能一个选项一个选项添加&#xff0c;效率较低&#xff0c;如何在表单设计中一次性添加多个关联选项&#xff1f; 示例代码&#xff1a; from django.contrib import adminfrom .models impo…
阅读更多...
game项目（梦开始的地方）

game项目（梦开始的地方）

梦开始的地方 由于easyx只支持vis&#xff0c;所以这个项目的书写以后都是在vis上进行&#xff0c;希望自己能够把这个项目好好完成&#xff0c;相信自己&#xff0c;加油&#xff01; 我们需要一个头文件来包括作图工具 (这个头文件在easyx上面下载) #include<graphics.…
阅读更多...
2024.2.21 模拟实现 RabbitMQ —— 实现转发规则

2024.2.21 模拟实现 RabbitMQ —— 实现转发规则

目录 需求分析 直接交换机&#xff08;Direct &#xff09; 主题交换机&#xff08;Topic &#xff09; 扇出交换机&#xff08;Fanout &#xff09; Topic 交换机转发规则 routingKey 组成 bindingKey 组成 匹配规则 情况一 情况二 情况三 实现 Router 类 校验 b…
阅读更多...
为新固态硬盘安装操作系统

为新固态硬盘安装操作系统

目录 背景方案具体步骤1 为新硬盘进行分区2 下载Dism3 下载win10的iso文件4 通过Dism 重装系统5 从biso调整启动顺序5 遗留问题 参考资料 背景 情况是这样的&#xff0c;我的电脑本来就有一块sata的固态硬盘&#xff0c;作为c盘&#xff0c;装载的是win10系统。 一方面只有500…
阅读更多...
滚雪球学Java(68)：全面了解Java中常用的集合类：LinkedHashMap的应用与实践

滚雪球学Java(68)：全面了解Java中常用的集合类：LinkedHashMap的应用与实践

咦咦咦&#xff0c;各位小可爱&#xff0c;我是你们的好伙伴——bug菌&#xff0c;今天又来给大家普及Java SE相关知识点了&#xff0c;别躲起来啊&#xff0c;听我讲干货还不快点赞&#xff0c;赞多了我就有动力讲得更嗨啦&#xff01;所以呀&#xff0c;养成先点赞后阅读的好…
阅读更多...
【JAVA高级面试题】运用锁机制实现一个自定义的阻塞队列

【JAVA高级面试题】运用锁机制实现一个自定义的阻塞队列

文章目录 前言实战演示写在最后 前言 前几天看见一个高级Java面试题&#xff0c;我觉得很有代表意义。既考察了面试者的基本锁机制运用&#xff0c;也了解了阻塞队列的产生实现原理。先分享出来&#xff0c;以供鉴赏。 面试题&#xff1a;实现一个自定义的阻塞队列&#xff0c…
阅读更多...
git@github.com: Permission denied (publickey).

git@github.com: Permission denied (publickey).

这个问题是使用git克隆自己的私有代码仓库时发现的&#xff0c;虚拟机中执行下面的指令生成了ssh私钥和公钥 ssh-keygen并且成功将公钥上传到了github上 但是执行git clone克隆私有仓库时依旧失败&#xff0c;报错内容和标题差不多 通过这个报错最终还是锁定了问题&#xff…
阅读更多...
牛客网 JZ53 数字在升序数组中出现的次数

牛客网 JZ53 数字在升序数组中出现的次数

思路&#xff1a; 因为是非降序数组&#xff0c;所以可以通过二分法快速排查范围&#xff0c;等mid值找到对应k时&#xff0c;只需要往前找有多少个k和往后找有多少个k&#xff0c;计算出总数即可 答案&#xff1a; int GetNumberOfK(int* nums, int numsLen, int k ) {int…
阅读更多...
程序员必备技能----删库跑路大总结

程序员必备技能----删库跑路大总结

删库跑路大总结&#xff0c;各个都是大杀器&#xff0c;破坏性太大&#xff0c;轻易不要尝试。 删除linux根目录&#xff0c;用户目录&#xff0c;其实还可以增加一个删除/etc。删除&#xff08;清除&#xff09;数据库。删除redis缓存和持久化文件。删除mongodb库。git push …
阅读更多...
Android 沉浸式状态栏

Android 沉浸式状态栏

过时的API //设置默认隐藏虚拟按键&#xff0c;虚拟按键显示后为半透明protected open fun hideNavigationBarAndFullScreen() {val flags: Int// This work only for android 4.4flags if (Build.VERSION.SDK_INT > Build.VERSION_CODES.KITKAT) {// This work only for a…
阅读更多...
Java面向对象（四）

Java面向对象（四）

一、面向对象特征&#xff08;三&#xff09;---多态 父类引用指向子类的对象&#xff0c;从而产生多种形态 例&#xff1a; Animal dog new Dog(); 同一种事物&#xff0c;在不同的时刻表现不同的状态前提&#xff1a;二者存在直接或间接的继承关系时&#xff0c;/*//装狗pu…
阅读更多...
SSH tunneling 简明示例

SSH tunneling 简明示例

基本概念 SSH tunneling又称为SSH port forwarding。 如果想快速了解其应用场景&#xff0c;这篇文章A short guide to SSH port forwarding 很不错。其详细解释了Client to Server的Local Forwarding。虽然没有涉及Server to Client的Remote Forwarding&#xff0c;但他也指…
阅读更多...
最新文章

Copyright @ 2022~2023