【数据结构:复杂度】时间复杂度
本节重点内容:
- 算法的复杂度
- 时间复杂度的概念
- 大O的渐进表示法
- 常见时间复杂度计算举例
⚡算法的复杂度
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的额外的空间。在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
复杂度在校招中的考察:

⚡时间复杂度的概念:
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数(数学),它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
总而言之:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。

实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要大概执行次数,那么这里我们使用大O的渐进表示法。
⚡大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
- 用常数1取代运行时间中的所有加法常数。
- 在修改后的运行次数函数中,只保留最高阶项。
- 如果最高阶项存在且不是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次找到。
- 平均情况:N/2次找到。
在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为O(N)。
⚡常见时间复杂度计算举例
实例1:
实例二:

实例三:

实例四:

实例五:

实例六:
实例七:


感谢大家能够看完这篇博客,创作时长,小伙伴们觉得我的博客对你有帮助,不妨留下你的点赞的收藏,关注我,带你了解不一样的C语言。

相关文章:
【数据结构:复杂度】时间复杂度
本节重点内容: 算法的复杂度时间复杂度的概念大O的渐进表示法常见时间复杂度计算举例⚡算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的&…...
京东pop店铺订单导出
下载安装与运行 下载、安装与运行 语雀 特别提醒 只能导出已登录店铺的订单导出的收件人手机号是虚拟号 功能 主要是方便线下工厂发货的店主 所见即所得的导出自由选择导出项自由排序Excel导出列顺序导出过程中有进度提示,用户可以随时提前中止 什么是所见即所…...
论文阅读:Towards Stable Test-time Adaptation in Dynamic Wild World
今天阅读ICLR 2023 ——Towards Stable Test-time Adaptation in Dynamic Wild World Keywords:Test-time adaptation (TTA); 文章目录Towards Stable Test-time Adaptation in Dynamic Wild WorldProblem:motivation:Contributio…...
2022国赛27:Linux-1时间服务chrony配置
大赛试题内容: 3.利用chrony配置Linux-1为其他Linux主机提供时间同步服务。 解答过程: 安装chrony服务[root@cs1 ~]# yum -y install chrony 配置/etc/chrony.conf文件[root@cs1 ~]# vi /etc/chrony.conf 7行改为 server 10.10.70.101 iburst 23行改为 去掉#号 allow 1…...
Java——二维数组中的查找
题目链接 牛客在线oj题——二维数组中的查找 题目描述 在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二…...
Android 9.0 添加关机铃声功能实现
1.前言 在9.0的系统rom定制化开发中,在原生系统中,关于开机铃声和关机铃声是默认不支持的,系统默认支持开机动画和关机动画等功能,所以关于增加开机铃声和关机 铃声的相关功能,需要自己增加相关的关机铃声功能 2.添加关机铃声功能实现的核心类 frameworks\base\cmds\boo…...
IPv4 和 IPv6 的组成结构和对比
IPv4 和 IPv6 的组成结构和对比IPv4IPv6互联网协议 (IP) 是互联网通信的基础,IP 地址是互联网上每个设备的唯一标识符。目前最常用的 IP 协议是 IPv4,它已经有近 30 年的历史了。然而,IPv4 存在一些问题,例如: 地址空间不足:IPv4 …...
Spring的事务管理
Spring的事务管理Spring的事务管理1、事务的回顾【1】事务的定义【2】事务的ACID原则2、spring事务API介绍【了解】【1】PlatformTransactionManager【1.1】PlatformTransactionManager作用【1.2】PlatformTransactionManager接口【1.3】PlatformTransactionManager实现类【2】…...
MCAL知识点(十六):VADC驱动配置详解(理论基础篇)
目录 1、概述 2、EB配置 2.1、通用界面配置 2.1.1、General 2.1.2、AdcConfigSet_0 2.1.3、AdcGlobinputClass 2.1.4、AdcHwUn...
MySQL--库的操作--校验规则对于数据库的影响--0409
目录 1.库的基础操作 查看数据库 创建数据库 删除数据库 查看建库语句 修改数据库 2.字符集和字符集校验规则 2.1 查看系统默认字符集以及校验规则 2.2 使用特定的字符集创建数据库 2.3 不同校验规则对数据库的影响 2.3.1 大小写验证 2.3.2 排序验证 3.备份和恢复 3.1…...
markdown-it基本使用
markdown-it能够将markdown语法的内容转换为html内容,这样我们使用markdown语法写的笔记,就可以转换作为网页使用了 Markdown语法 Markdown语法图文全面详解(10分钟学会) 基础使用 安装markdown-it npm install markdown-it --save使用markdown-it …...
CMake入门教程【核心篇】8.3对象库
文章目录 知识点实例代码目录代码实现知识点 add_library(libhello OBJECT src/hello.cpp)使用OBJECT 参数可以把对象传入到libhello 中,且不会生成.lib文件 使用变量$<TARGET_OBJECTS:libhello>即可获取,比较实用 实例 代码目录 |-📁prj10 |-- 🎴CMakeLists…...
单片机_CT107D训练平台电路原理图\蓝桥杯训练板\IO扩展模块\74HC138译码器
74HC138译码器(实现3个IO口控制8个引脚实现IO口的扩展) 配置信号放大模块,可以对输入的低电压模拟信号进行放大; 配置 138 译码器,可以做译码实验; 外设可以用存储器映射方式访问,也可以直接控…...
Rabbitmq消息确认机制
1.生产者确认机制 确认消息发送到交换机--Confirm方式 1.1普通Confirm方式 private static void sendMsg(Channel channel) throws IOException, InterruptedException { //开启确认机制 channel.confirmSelect(); //发送消息到exchange St…...
FinClip 云开发实践(附小程序demo)
在开发一个小程序时,除了考虑界面功能逻辑外,还需要后端的数据支持,开发者需要提前考虑服务器、存储和数据库等相关需求的支持能力,此外还可能需要花费时间精力在部署应用、和依赖服务的建设上。 因此,腾讯小程序为…...
真正好用的工业品ERP系统应该是什么样的?
一个好用的进销存ERP系统应该有以下特点: 1. 全面覆盖企业经营流程,包括采购、销售、库存、财务等模块,能够实现全方位的管理和控制。 2. 自定义配置,灵活地适应大多数用户的需求。 3. 数据精准、实时化,支持统计分…...
Shiro重定向
使用了统一认证,然后每次登录,不能定向到用户指定的界面,非得回到首页,所以做了如下改动 1、在FormAuthenticationFilter中在issueSuccessRedirect中加上五句话。 Overrideprotected void issueSuccessRedirect(ServletRequest …...
Greenplum数据库执行器——PartitionSelector执行节点
为了能够对分区表有优异的处理能力,对于查询优化系统来说一个最基本的能力就是做分区裁剪partition pruning,将query中并不涉及的分区提前排除掉。如下执行计划所示,由于单表谓词在parititon key上,在优化期间即可确定哪些可以分区…...
POJ 2311 Cutting Game
POJ 2311 Cutting Game 题目大意 有一张有whw\times hwh个格子的长方形纸张,两个人轮流将当前的纸张中选一张,并沿着格子的边界将这张纸剪成两部分。最先切出只有一个格子的纸张(111\times 111的纸张)的玩家获胜。当双方都采用最…...
CTF-PHP反序列化漏洞1-基础知识
作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
怎么开发一个网络协议模块(C语言框架)之(六) ——通用对象池总结(核心)
+---------------------------+ | operEntryTbl[] | ← 操作对象池 (对象数组) +---------------------------+ | 0 | 1 | 2 | ... | N-1 | +---------------------------+↓ 初始化时全部加入 +------------------------+ +-------------------------+ | …...
