当前位置: 首页 > news >正文

数据结构-算法的时间复杂度(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 举例说明&#xff1a; 写在最后&#xff1a; 1. 算法效率 我们该如何判断一个算法的好坏&#xff1f; 衡量一个算法的好坏&#xff0c;是从时间和空间两个维度比较的&#xff0c; 而今天…...

Cygwin安装与Mingw

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

教育舆情监测方案有哪些,TOOM讲解教育舆情的应对与处理?

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

c语言操作文件

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

【C语言】初识指针

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

FFMPEG自学一 音视频解封装

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

HoloLens 2 丨打包丨MRTK丨Unity丨新手教学

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

AcWing语法基础课笔记 第四章 C++中的数组

第四章 C中的数组 程序 逻辑 数据&#xff0c;数组是存储数据的强而有力的手段。 ——闫学灿 一维数组 数组的定义 数组的定义方式和变量类似。 数组的初始化 在main函数内部&#xff0c;未初始化的数组中的元素是随机的。 访问数组元素 通过下标访问数…...

UTF小结

运行测试 编辑测试 运行模式&#xff1a;程序集Platform平台选择 Any Platforms编辑模式&#xff1a;程序集Platform平台选择 Editor 特性 Test、UnityTest特性&#xff1a;测试方法需要添加Test或UnityTest特性&#xff0c;测试方法是公有的SetUp、TearDown特性&#xff1a…...

(考研湖科大教书匠计算机网络)第四章网络层-第六节3:开放最短路径优先OSPF的基本工作原理

获取pdf&#xff1a;密码7281专栏目录首页&#xff1a;【专栏必读】考研湖科大教书匠计算机网络笔记导航 文章目录一&#xff1a;OSPF概述&#xff08;1&#xff09;概述&#xff08;2&#xff09;细节阐述A&#xff1a;链路状态和代价B&#xff1a;问候分组和邻居表C&#xff…...

积水在线监测仪——积水点、易涝点水位监测设备

一、设备概述 积水在线监测仪是一款用于城市积水点、易涝点等场景的水位监测设备&#xff0c;设备采用电池供电&#xff0c;无需另外供电&#xff0c;安装方便&#xff0c;使用简单。可以时监测水点、易涝点水位情况&#xff0c;当水位数据超过阈值后触发告警上传&#xff0c;…...

DCMM认证机构

一、什么是DCMM DCMM认证&#xff0c;又称为数据管理能力成熟度评估&#xff0c;依据 都是GB/T -《数据管理能力成熟度评估模型》&#xff0c;这是我国首个数据管理领域的国家标准&#xff0c;由国家质量监督检验检疫总局、国家标准化管理委员会于年3月15日正式发布。DCMM认证…...

Golang基于文件魔数判断文件类型

本文介绍基于魔数判断文件类型&#xff0c;涉及文件查找读取内容、文件魔数、字节比较&#xff0c;最后还介绍函数参数的知识。 查找位置 File.Seek()函数可以设置偏移位置&#xff0c;为下一次读或写确定偏移量&#xff0c;具体起点有whence确定&#xff1a;0标识相对文件开始…...

MySQL——索引视图练习题

学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;SC (Sno, Cno, Score)…...

哈希表题目:矩阵置零

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

HTTP API自动化测试从手工到平台的演变

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

【从零开始学C语言】知识总结一:C语言的基本知识汇总

C语言期末知识点总结 C语言期末试题&#xff08;附答案&#xff09;选择题编程题 2022C语言知识点大全【详细、必备】 C语言期末大作业-学生成绩管理系统&#xff08;完整源码设计报告&#xff09; C语言期末作业&#xff08;15个&#xff09;-货物管理系统、歌曲信息管理系…...

CAD二次开发 添加按钮Ribbon

这篇文章是教大家怎样子创建自己的Ribbon按钮界面&#xff08;如下图&#xff09;&#xff0c;以下示例代码在CAD2020中运行实现。 背景 创建一个属于自己的Ribbon按钮&#xff08;如下图&#xff09; 理解Ribbon、Panel、Tab的关系&#xff08;如下图&#xff09;&#xff…...

[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 设计&#xff0c;而一个设计不够完善的 API 则注定会导致系统的后续发展和维护非常困难。在关键环节制定明确的 API 规范有助于 Service 对内提高产品间互通的效率&#xff0c;对外提供一致的使用体…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...