数据结构时间复杂度与空间复杂度
文章目录
- 引入
- 算法
- 1、时间复杂度
- 1.概念
- 2.大O渐进表示法
- 3.常见时间复杂度计算举例
- 2、空间复杂度
- 1.概念
- 2.常见空间复杂度计算举例
引入
算法
算法就是一段能将一个物体从初始状态转换到某个目标转态的一个有限长序列方法的统称
算法效率:考虑一个方法是否好,就要从它的效率上考虑,能高质量(即高效)的完成目标的算法,就是一个好的算法;而对于算法效率要怎么来进行判定呢?
与算法效率有关的因素有很多,包括:算法所需的时间、空间成本等因素;在计算机相关中包括网络运行速度,硬件等因素都会对效率产生影响,而这些因素都是我们所无法掌控的,所以我们在进行算法效率评定中大致以所需的时间和空间作为主要的衡量标志,来对算法效率进行一个判定,这就是时间复杂度与空间复杂度。
1、时间复杂度
1.概念
在计算机中,算法的时间复杂度也有定量的函数,其实也就是他将目标从初始状态转换为目标状态所需花费的时间。就从理论上来讲,想要获取一个算法的时间复杂度,那就必须将在计算机上运行,然后测量所需的时间,才能计算出它的时间复杂度。但在实际生活中,这种方式较为难以实现,所以我们将算法中基本操作的执行次数来作为它的时间复杂度。
我们就以下方的代码来进行一个举例:
//请计算Test1中++count所执行的次数
void Test1(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);
}
在如上代码中++count一共执行了:N^2 + 2N + 10次
实际上我们计算算法的时间复杂度时,并不需要将准确的执行次数计算出来,而是只需要渐进的表示。因为当你将量级拉大,比如几十万、几百万次执行中,几十、几百次的执行次数对于整体来说影响也不大。我们通常使用的方法是大O渐进表示法。
2.大O渐进表示法
1.表示方法:O(表达式中影响最大的哪一项)
2.推荐大O表示法
1)确定的常数次,我们都使用O(1) 来表示;原因:只要是常数次,它就不是未知数的影响,无论基数多大,它都不会变,意味着效率不变
2)O(N) 意味着随着N的变化,运算时间变长
3)对于有些会有最好情况、最坏情况、与平均情况,这时候的时间复杂度是保守的估算,取最坏结果
3.注意:
1)不是说一次循环就是O(n),两次循环就是o(n^2),具体要通过程序区分析
2)时间复杂度计算,不能去数代码执行的次数,要根据思想去计算时间复杂度,然后看哪个更优,再去实现
4.常见的时间复杂度:O(N^2) , O(N) , O(logN) , O(1)
3.常见时间复杂度计算举例
void Test2(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);
}void Test3(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);
}
Test2就是刚刚我们所计算的那道题,用大O表示法来进行表示,它的时间复杂度是:O(N^2)
Test3中基本操作执行了M+N次,有两个未知数M和N,时间复杂度为 O(N+M)
2、空间复杂度
1.概念
空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。
在当今世界中由于电脑,手机等的储存空间大大增加,所以我们在实际处理问题中对与时间复杂度考虑式要优先于空间复杂度的。
2.常见空间复杂度计算举例
// 计算BubbleSort的空间复杂度?
void Test4(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;}
}// 计算阶乘递归Fac的空间复杂度?
long long Test5(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}
Test4中使用了常数个额外空间,所以空间复杂度为 O(1)
Test5中递归调用了N次,开辟了N个栈帧,每个栈帧使用了常数个空间。空间复杂度为O(N)
相关文章:
数据结构时间复杂度与空间复杂度
文章目录 引入算法 1、时间复杂度1.概念2.大O渐进表示法3.常见时间复杂度计算举例 2、空间复杂度1.概念2.常见空间复杂度计算举例 引入 算法 算法就是一段能将一个物体从初始状态转换到某个目标转态的一个有限长序列方法的统称 算法效率:考虑一个方法是否好&…...
【计算机网络】内容整理
概述 分组交换 分组交换则采用存储转发(整个包必须到达路由器,然后才能在下一个链路上传输)技术。 在发送端,先把较长的报文划分成较短的、固定长度的数据段。 电路交换 在端系统间通信会话期间,预留了端系统间沿路径通信所需…...
【K12】Python写分类电阻问题的求解思路解析
分压电阻类电路问题python程序写法 一个灯泡的电阻是20Ω,正常工作的电压是8V,正常工作时通过它的电流是______A。现在把这个灯泡接到电压是9V的电源上,要使它正常工作,需要给它______联一个阻值为______的分压电阻。 解决思想 …...
数据库面经---10则
数据库范式有哪些: 第一范式(1NF): 数据表中的每一列都是不可分割的原子值。每一行数据在关系表中都有唯一标识,通常是通过主键来实现。第二范式(2NF): 满足第一范式。…...
深度学习基本介绍-李沐
目录 AI分类:模型分类:广告案例: bilibili视频链接:https://www.bilibili.com/video/BV1J54y187f9/?p2&spm_id_frompageDriver&vd_sourcee6a6e7fec41c59c846c142eb5ef1da0b AI分类: 模型分类: 图…...
【上分日记】第369场周赛(分类讨论 + 数学 + 前缀和)
文章目录 前言正文1.3000. 对角线最长的矩形的面积2.3001. 捕获黑皇后需要的最少移动次数3.3002. 移除后集合的最多元素数3.3003. 执行操作后的最大分割数量 总结尾序 前言 终于考完试了,考了四天,也耽搁了四天,这就赶紧来补这场周赛的题了&a…...
CMake Error at CMakeLists.txt:14 (project): The CMAKE_CXX_COMPILER:
报错 CMake Error at CMakeLists.txt:14 (project):The CMAKE_CXX_COMPILER:arm-none-eabi-g 解决办法1 Arm GNU Toolchain Downloads – Arm Developer x86_64 linux上: x86_64 Linux hosted cross toolchains AArch32 bare-metal target (arm-none-eabi)arm-g…...
Sqoop与其他数据采集工具的比较分析
比较Sqoop与其他数据采集工具是一个重要的话题,因为不同的工具在不同的情况下可能更适合。在本博客文章中,将深入比较Sqoop与其他数据采集工具,提供详细的示例代码和全面的内容,以帮助大家更好地了解它们之间的差异和优劣势。 Sq…...
Pandas实战100例 | 案例 31: 转换为分类数据
案例 31: 转换为分类数据 知识点讲解 在处理包含文本数据的 DataFrame 时,将文本列转换为分类数据类型通常是一个好主意。这可以提高性能并节省内存。Pandas 允许将列转换为 category 类型。 分类数据类型: category 类型适用于那些只包含有限数量不同值的列&…...
椋鸟C语言笔记#33:文件的顺序读写
萌新的学习笔记,写错了恳请斧正。 目录 光标(文件位置指示器) 文件的顺序读写 fgetc 使用实例 fputc 使用实例 fgets fputs 使用实例 fscanf fprintf fread fwrite 使用实例 光标(文件位置指示器) 我们…...
Transformer - Attention is all you need 论文阅读
虽然是跑路来NLP,但是还是立flag说要做个project,结果kaggle上的入门project给的例子用的是BERT,还提到这一方法属于transformer,所以大概率读完这一篇之后,会再看BERT的论文这个样子。 在李宏毅的NLP课程中多次提到了…...
安装配置Flink
安装配置Flink 1.上传安装包到Linux 2.解压到指定路径 tar -zxf ./flink-1.14.0-bin-scala_2.12.tgz /usr/local/src/3.修改环境变量 vi ~/.bashrc#往最后加入 export FLINK_HOME /usr/local/src/flink-1.14.0/ export PATH$PATH:$FLINK_HOME/bin#激活环境变量 source ~/.…...
解决Spss没有创建虚拟变量的选项的问题
这个是今天用spss想创建虚拟变量然后发现我的spss没有。 然后能怎么办我就百度呗, 说是在扩展里连接扩展中心 天哪,谁能连上,我连不上 于是就找到了从github上下载到本地,然后安装到spss中 目录 解决方法 点击code 再点击D…...
wxWidgets实战:使用mpWindow绘制阻抗曲线
选择模型时,需要查看model的谐振频率,因此需要根据s2p文件绘制一张阻抗曲线。 如下图所示: mpWindow 左侧使用mpWindow,右侧使用什么? wxFreeChart https://forums.wxwidgets.org/viewtopic.php?t44928 https://…...
深度学习15—(迁移学习)冻结和解冻神经网络模型的参数
冻结与解冻代码: def freeze_net(net):if not net:returnfor p in net.parameters():p.requires_grad Falsedef unfreeze_net(net):if not net:returnfor p in net.parameters():p.requires_grad True 这段代码定义了两个函数:freeze_net 和 unfree…...
强化学习应用(八):基于Q-learning的无人机物流路径规划研究(提供Python代码)
一、Q-learning简介 Q-learning是一种强化学习算法,用于解决基于马尔可夫决策过程(MDP)的问题。它通过学习一个价值函数来指导智能体在环境中做出决策,以最大化累积奖励。 Q-learning算法的核心思想是通过不断更新一个称为Q值的…...
常见面试题之HTML
行内元素有哪些?块级元素有哪些? 空(void)元素有那些? HTML 中的行内元素(inline elements)通常用于在一行内显示,不会独占一行的空间。常见的行内元素有: <span>:用于对文本…...
数据结构与算法教程,数据结构C语言版教程!(第三部分、栈(Stack)和队列(Queue)详解)六
第三部分、栈(Stack)和队列(Queue)详解 栈和队列,严格意义上来说,也属于线性表,因为它们也都用于存储逻辑关系为 "一对一" 的数据,但由于它们比较特殊,因此将其单独作为一章,做重点讲解。 使用栈…...
使用Docker部署PDF多功能工具Stirling-PDF
1.服务器上安装docker 安装比较简单,这种安装的Docker不是最新版本,不过对于学习够用了,依次执行下面命令进行安装。 sudo apt install docker.io sudo systemctl start docker sudo systemctl enable docker 查看是否安装成功 $ docker …...
linux安装系统遇到的问题
这两天打算攻克下来网络编程,发现这也确实是很重要的一个东西,但我就奇了怪了,老师就压根没提,反正留在我印象的就一个tcp/ip七层网络。也说正好,把linux命令也熟悉熟悉,拿着我大一课本快速过过 连接cento…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...
【Linux】Linux 系统默认的目录及作用说明
博主介绍:✌全网粉丝23W,CSDN博客专家、Java领域优质创作者,掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围:SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...
