数据结构-算法的时间复杂度(1.1)
目录
1. 算法效率
2. 时间复杂度
2.1 时间复杂度的概念
2.2 大O的渐进表示法
2.3 举例说明:
写在最后:
1. 算法效率
我们该如何判断一个算法的好坏?
衡量一个算法的好坏,是从时间和空间两个维度比较的,
而今天,我就来详细探讨一下时间复杂度。
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度是一个函数,
而:
算法中的基本操作的执行次数,为算法的时间复杂度。
我们当然不能只用运行一段程序的速度来解释时间复杂度,
毕竟每个人电脑的CPU运行速度不同。
例:
#include <stdio.h>int main()
{int n = 10;while (n > 0){n--;}return 0;
}
这一段代码走了10次,
他的时间复杂度是O(1)。
例2:
#include <stdio.h>int main()
{int n;scanf("%d", &n);while (n > 0){n--;}return 0;
}
这段代码走了n次,
他的时间复杂度是O(N)。
那么问题来了,时间复杂度究竟是怎么求的?
2.2 大O的渐进表示法
规则:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
2.3 举例说明:
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);
}
这段代码前面是2*N次,后面是10次,
加起来是2*N+10,
而他的时间复杂度是O(N)
例2:
冒泡排序的时间复杂度:
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),
而最坏的情况是要和每一个数比较交换,是O(N^2)。
所以他的时间复杂度是O(N^2)。
例3:
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
斐波那契递归的时间复杂度是O(2^N)。
通过上述的例子,我们可以知道的是,
计算时间复杂度,计算的是该算法最坏的情况。
写在最后:
以上就是本篇文章的内容了,感谢你的阅读。
如果喜欢本文的话,欢迎点赞和评论,写下你的见解。
如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。
之后我还会输出更多高质量内容,欢迎收看。
相关文章:
数据结构-算法的时间复杂度(1.1)
目录 1. 算法效率 2. 时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3 举例说明: 写在最后: 1. 算法效率 我们该如何判断一个算法的好坏? 衡量一个算法的好坏,是从时间和空间两个维度比较的, 而今天…...

Cygwin安装与Mingw
共同点:window下编译环境 区别:cygwin(gnu windows)模拟Linux编译环境, mingw模拟window编译环境,生成.exe可执行文件 目录 Cygwin安装 一、官网下载 二、双击安装 三、选择安装路径后,到连接方式如图 四、添加连…...

教育舆情监测方案有哪些,TOOM讲解教育舆情的应对与处理?
教育舆情方案是针对教育领域的舆情事件或问题而制定的应对方案。其主要目的是通过有效的信息收集、分析、处理和传播,帮助教育机构或相关组织及时掌握和应对公众舆论的发展趋势,维护良好的舆情形象和声誉,教育舆情监测方案有哪些,…...

c语言操作文件
1、文件缓冲区 文件缓冲区的目的:提高访问效率 提高磁盘使用寿命 刷新就是将当前缓冲区数据全部提交。 不刷新时,程序在崩溃时缓冲区内容无法输出(有些情形会带来错误) 文件缓冲区的四种刷新方式 行刷新(遇到换行符…...

【C语言】初识指针
目录 一、指针是什么 二、指针和指针类型 三、野指针 四、指针运算 五、指针和数组 六、二级指针 七、指针数组 一、指针是什么 指针就是内存地址,指针变量是用来存放内存地址的变量,在同一CPU构架下,不同类型的指针变量所占用的存储单元长度…...

FFMPEG自学一 音视频解封装
一、音视频包含哪些数据对于一个mp4文件我们可以通过音视频分析软件打开查看内部信息。从两图可以看出mp4文件一般包含 音频流 视频流等。对于上面的字段大致分析如下Format编码方式AVC现在大部分视频都是这种编码方式,即H264。CodecId编码器idavc1H264封装有2种格式…...

HoloLens 2 丨打包丨MRTK丨Unity丨新手教学
HoloLens 2打包流程制作前言开发工具介绍Visual Studio 2019MRTK插件或示例程序下载打包流程介绍Unity操作修改Visual Studio修改Hololens 修改Hololens 密码忘记总结前言 提示:今日功能介绍 使用 MRTK制作hololens 2的打包流程制作的新手教学。 开发工具介绍 这…...

AcWing语法基础课笔记 第四章 C++中的数组
第四章 C中的数组 程序 逻辑 数据,数组是存储数据的强而有力的手段。 ——闫学灿 一维数组 数组的定义 数组的定义方式和变量类似。 数组的初始化 在main函数内部,未初始化的数组中的元素是随机的。 访问数组元素 通过下标访问数…...
UTF小结
运行测试 编辑测试 运行模式:程序集Platform平台选择 Any Platforms编辑模式:程序集Platform平台选择 Editor 特性 Test、UnityTest特性:测试方法需要添加Test或UnityTest特性,测试方法是公有的SetUp、TearDown特性:…...

(考研湖科大教书匠计算机网络)第四章网络层-第六节3:开放最短路径优先OSPF的基本工作原理
获取pdf:密码7281专栏目录首页:【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一:OSPF概述(1)概述(2)细节阐述A:链路状态和代价B:问候分组和邻居表Cÿ…...

积水在线监测仪——积水点、易涝点水位监测设备
一、设备概述 积水在线监测仪是一款用于城市积水点、易涝点等场景的水位监测设备,设备采用电池供电,无需另外供电,安装方便,使用简单。可以时监测水点、易涝点水位情况,当水位数据超过阈值后触发告警上传,…...
DCMM认证机构
一、什么是DCMM DCMM认证,又称为数据管理能力成熟度评估,依据 都是GB/T -《数据管理能力成熟度评估模型》,这是我国首个数据管理领域的国家标准,由国家质量监督检验检疫总局、国家标准化管理委员会于年3月15日正式发布。DCMM认证…...
Golang基于文件魔数判断文件类型
本文介绍基于魔数判断文件类型,涉及文件查找读取内容、文件魔数、字节比较,最后还介绍函数参数的知识。 查找位置 File.Seek()函数可以设置偏移位置,为下一次读或写确定偏移量,具体起点有whence确定:0标识相对文件开始…...

MySQL——索引视图练习题
学生表:Student (Sno, Sname, Ssex , Sage, Sdept) 学号,姓名,性别,年龄,所在系 Sno为主键 课程表:Course (Cno, Cname,) 课程号,课程名 Cno为主键 学生选课表:SC (Sno, Cno, Score)…...

哈希表题目:矩阵置零
文章目录题目标题和出处难度题目描述要求示例数据范围进阶解法一思路和算法代码复杂度分析解法二思路和算法代码复杂度分析解法三思路和算法代码复杂度分析题目 标题和出处 标题:矩阵置零 出处:73. 矩阵置零 难度 3 级 题目描述 要求 给定一个 m…...

HTTP API自动化测试从手工到平台的演变
不管是 Web 系统,还是移动 APP,前后端逻辑的分离设计已经是常态化,相互之间通过 API 调用进行数据交互。在基于 API 约定的开发模式下,如何加速请求 / 响应的 API 测试,让研发人员及早参与到调试中来呢?既然…...

【从零开始学C语言】知识总结一:C语言的基本知识汇总
C语言期末知识点总结 C语言期末试题(附答案)选择题编程题 2022C语言知识点大全【详细、必备】 C语言期末大作业-学生成绩管理系统(完整源码设计报告) C语言期末作业(15个)-货物管理系统、歌曲信息管理系…...

CAD二次开发 添加按钮Ribbon
这篇文章是教大家怎样子创建自己的Ribbon按钮界面(如下图),以下示例代码在CAD2020中运行实现。 背景 创建一个属于自己的Ribbon按钮(如下图) 理解Ribbon、Panel、Tab的关系(如下图)ÿ…...
[RK3568 Android12] 添加自定义启动脚本
1:定义添加的脚本 比如为displayn2k.sh #!/system/bin/sh log "displayn2k.sh begin running" sleep 5 log "displayn2k.sh sleep 8" sleep 5 log "================sleep finished==========================" #remount /system/bin/mount -o …...
API 体系构建
前言 API 是模块或者子系统之间交互的接口定义。好的系统架构离不开好的 API 设计,而一个设计不够完善的 API 则注定会导致系统的后续发展和维护非常困难。在关键环节制定明确的 API 规范有助于 Service 对内提高产品间互通的效率,对外提供一致的使用体…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
区块链技术概述
区块链技术是一种去中心化、分布式账本技术,通过密码学、共识机制和智能合约等核心组件,实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点:数据存储在网络中的多个节点(计算机),而非…...