时间复杂度
一、时间复杂度
时间复杂度是计算机科学中用来衡量算法运行时间随输入规模增加而增长的速度。简单来说,它是一个衡量算法执行效率的指标,表示算法运行所需时间与输入数据量之间的关系。
时间复杂度通常用大O符号(O)来表示,例如:O(1)、O(n)、O(n^2)等。这些符号描述了算法在最坏情况下执行的时间与输入规模之间的关系。其中:
-
O(1) 表示算法的执行时间是常数,不随输入规模变化而变化。即使输入数据量增加,算法的执行时间也保持恒定。
-
O(n) 表示算法的执行时间与输入规模线性增长,即输入规模增加一倍,执行时间也增加一倍。
-
O(n^2) 表示算法的执行时间与输入规模的平方成正比,即输入规模增加一倍,执行时间会增加四倍。
时间复杂度的理解帮助我们评估不同算法的效率,我们会尽量选择时间复杂度较低的算法,以获得更快的执行速度。
时间复杂度是对算法执行时间的一个抽象估计,它并不考虑硬件和编译器等因素对执行时间的影响。因此,时间复杂度只是一种相对的比较方式,而不是精确的执行时间。
二、(O)表达式含义
O(1)、O(n)、O(n^2) 等是描述算法时间复杂度的表示方式,它们反映了算法执行时间与输入规模的关系。以下是这些符号的具体定义:
-
O(1):常数时间复杂度。表示算法的执行时间是一个常数,不随输入规模的增加而改变。无论输入数据量多少,执行时间都保持恒定。
-
O(n):线性时间复杂度。表示算法的执行时间与输入规模成线性关系。如果输入数据量增加一倍,执行时间也会增加一倍。
-
O(n^2):平方时间复杂度。表示算法的执行时间与输入规模的平方成正比。如果输入数据量增加一倍,执行时间会增加四倍。
-
O(log n):对数时间复杂度。表示算法的执行时间与输入规模的对数成正比。在每一步操作中,算法可以将问题规模减少一半。
-
O(n log n):线性对数时间复杂度。表示算法的执行时间与输入规模的对数和线性的乘积成正比。常见于某些高效的排序算法,如:快速排序和归并排序。
-
O(m*n):多项式时间复杂度。表示算法的执行时间与输入规模的两个不同维度成正比。这是一种常见的在多维数据结构中的复杂度。
这些时间复杂度表示法帮助我们对不同算法的性能进行比较和评估,选择合适的算法来解决特定的问题。在进行算法分析和设计时,了解时间复杂度的含义和计算方法非常重要。
三、在实际过程中,如何估算时间复杂度?
在实际过程中,估算算法的时间复杂度可以通过以下方法进行:
-
计数基本操作: 首先,识别算法中的基本操作,如循环、条件判断、赋值等。然后,对这些基本操作进行计数,以了解算法在执行过程中涉及的基本操作次数。
-
确定输入规模: 确定算法的输入规模,通常用变量 n 表示。这可以是数据集的大小、数组的长度、输入元素的数量等。
-
分析循环次数: 如果算法中包含循环结构,分析循环的迭代次数。这通常涉及到输入规模 n,并考虑最坏情况下循环的迭代次数。
-
建立复杂度表达式: 将基本操作次数表示为输入规模 n 的函数,然后使用大O符号来表示算法的时间复杂度。
-
简化表达式: 对复杂度表达式进行简化,通常只保留最高项,去掉低次项和常数项。这样可以得到更为简洁的复杂度表示。
-
评估最坏情况: 时间复杂度通常估算算法在最坏情况下的执行时间。因此,需要考虑循环、条件等结构在最坏情况下的操作次数。
-
进行渐进分析: 时间复杂度分析更关注随着输入规模增加,算法执行时间的增长趋势。因此,进行渐进分析,关注算法的增长率。
-
比较不同算法: 如果有多个算法可以解决同一个问题,比较它们的时间复杂度,选择复杂度更低的算法。
-
实际测试验证: 估算的时间复杂度可以通过实际的测试和性能分析来验证。运行算法在不同输入规模下的实际执行时间,与估算的时间复杂度进行比较。
需要注意的是,时间复杂度是对算法执行时间的一个抽象估计,它不考虑具体硬件、编译器等因素对执行时间的影响。因此,在实际应用中,估算的时间复杂度可以作为指导,但实际执行时间可能会受到多种因素的影响。
四、案例分析
当分析时间复杂度时,让我们考虑以下几个案例:
-
案例:线性查找
def linear_search(arr, target):for num in arr:if num == target:return Truereturn False
在这个案例中,我们有一个线性查找算法,它遍历数组来查找目标元素。最坏情况下,如果目标元素不在数组中,需要遍历整个数组。因此,时间复杂度为 O(n),其中 n 是数组的长度。
-
案例:插入排序
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]j -= 1arr[j + 1] = key
插入排序算法将数组中的元素逐个插入已排序的部分。在最坏情况下,当数组逆序排列时,每个元素都需要移动到数组的开头,因此需要执行更多操作。时间复杂度为 O(n^2),其中 n 是数组的长度。
-
案例:归并排序
def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half):if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1
归并排序算法将数组分成两半,递归地排序每个子数组,然后将它们合并。无论输入数据的顺序如何,归并排序的时间复杂度始终为 O(n log n)。
这些案例展示了不同类型的算法及其时间复杂度。通过对基本操作次数和输入规模的分析,我们可以更好地理解不同算法的效率和性能。
相关文章:
时间复杂度
一、时间复杂度 时间复杂度是计算机科学中用来衡量算法运行时间随输入规模增加而增长的速度。简单来说,它是一个衡量算法执行效率的指标,表示算法运行所需时间与输入数据量之间的关系。 时间复杂度通常用大O符号(O)来表示&#…...

Unity实现广告滚动播放、循环播放、鼠标切换的效果
效果: 场景结构: 特殊物体:panel下面用排列组件horizent layout group放置多个需要显示的面板,用mask遮罩好。 using System.Collections; using System.Collections.Generic; using DG.Tweening; using UnityEngine; using Unity…...

LangChain + Streamlit + Llama:将对话式AI引入本地机器
推荐:使用 NSDT场景编辑器 助你快速搭建可二次编辑的3D应用场景 什么是LLMS? 大型语言模型 (LLM) 是指能够生成与人类语言非常相似的文本并以自然方式理解提示的机器学习模型。这些模型使用包括书籍、文章、网站和其他来源在内的…...
Python 读写 Excel 文件库推荐和使用教程
文章目录 前言Python 读写 Excel 库简介openpyxl 处理 Excel 文件教程pandas 处理 Excel 文件教程总结 前言 Python 读写 Excel 文件的库总体看还是很多的, 各有其优缺点, 以下用一图总结各库的优缺点, 同时对整体友好的库重点介绍其使用教程…...
“深入解析JVM:理解Java虚拟机的工作原理和优化技巧“
标题:深入解析JVM:理解Java虚拟机的工作原理和优化技巧 摘要:本文将深入探讨Java虚拟机(JVM)的工作原理和优化技巧。我们将从JVM的基本结构开始,逐步介绍其工作原理,并提供一些实际示例代码&am…...

解决SEGGER Embedded Studio无法显示Nordic MCU外设寄存器问题
如果使用SES调试NRF52840的时候发现,官方例程只能显示CPU寄存器,但是无法显示外设寄存器时,解决办法如下: 1.在解决方案右键→Options→Debug→Debugger,然后Target Device选择正确的型号。 2.Register Definition Fil…...
Oracle-day1:scott用户、查询、取整、截取、模糊查询、别名——23/8/23
整理一下第一天软件测试培训的知识点 1、scott用户 -- 以system管理员登录锁定scott用户 alter user scott account lock;-- 以system管理员登录解锁scott用户 alter user scott account unlock;-- 以system管理员用户设置scott用户密码 alter user scott identfied by tiger…...

stm32之3.key开关
假设key电阻为40kΩ,则key0 的电压3.3v*4/52.64v 2.key开关代码 ② GPIO_OType_PP//推挽输出 GPIO_OType_PP//开漏输出 推挽输出是指输出端口可以同时提供高电平和低电平输出,而开漏输出则是指输出端口只能提供低电平输出,高电平时需要借…...
GPT带我学-设计模式-代理模式
什么是代理模式 代理模式(Proxy Pattern)是设计模式中的一种结构型模式,它为其他对象提供一种代理以控制对这个对象的访问。 代理模式有三个主要角色:抽象主题(Subject)、真实主题(Real Subje…...

VMware Workstation Pro 无法使用开机状态下拍的快照来克隆虚拟机,怎么解决?
环境: VMware Workstation Pro16.0 Win10 专业版 问题描述: VMware Workstation Pro有台虚拟机在开机状态下拍了个6.7快照这个win10初始版,现在想在这个快照下直接克隆,无法使用开机状态下拍的快照创建克隆 解决方案: 1.关闭当前虚拟机 2.到虚拟机文件夹复制一份Wind…...
【JAVA】XML及其解析技术、XML检索技术、设计模式
XML XML(Extensible Markup Language)是可扩展标记语言的缩写,它是一种数据表示格式,可以描述复杂的数据结构,常用于传输和存储数据 作用: 用于进行存储数据和传输数据作为软件的配置文件 第一行是文档声明 <?xml version&q…...

Ansible 自动化安装软件
例子如下: 创建一个名为/ansible/package.yml 的 playbook : 将 php 和 mariadb 软件包安装到 dev、test 和 prod 主机组中的主机上 将 RPM Development Tools 软件包组安装到 dev 主机组中的主机上 将 dev 主机组中主机上的所有软件包更新为最新版本 --- - name:…...
简单介绍 React Native 整合 Formik 实现表单校验
Formik 是 React 和 React Native 开源表单库,Formik 负责处理重复且烦人的事情——跟踪值/错误/访问的字段、编排验证和处理提交——所以您不必这样做。而简化字段校验的话我们可以使用yup工具来实现。 首先安装Formik 和 Yup npm i formik npm i yupFormik 与 R…...

蓝帽杯半决赛2022
手机取证_1 iPhone手机的iBoot固件版本号:(答案参考格式:iBoot-1.1.1) 直接通过盘古石取证 打开 取证大师和火眼不知道为什么都无法提取这个 手机取证_2 该手机制作完备份UTC8的时间(非提取时间):(答案…...

电路学习+硬件每日学习十个知识点(40)23.8.20 (希腊字母读音,阶跃信号和冲激信号的关系式,信号的波形变换,信号的基本运算,卷积积分,卷积和)
文章目录 1.信号具有时间特性和频率特性。2.模拟转数字,抽样、量化、编码3.阶跃信号和冲激信号4.信号的波形变换(时移、折叠、尺度变换)5.信号的基本运算(加减、相乘、微分与积分、差分与累加)5.1 相加减5.2 相乘5.3 微…...

Python——列表(list)推导式
本文基于python3。 目录 1、Python推导式2、列表(list)推导式2.1、定义2.2、实际操作2.2.1、一个表达式,后面为一个 for 子句2.2.2、一个表达式,后面为一个 for 子句,然后,跟着if 子句。2.2.3、一个表达式,后面为一个…...
代码随想录算法训练营day43 | LeetCode 1049. 最后一块石头的重量 II 494. 目标和 474. 一和零
1049. 最后一块石头的重量 II(题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台) 思路:把全部石头重量加起来,然后除以二,就等于背包的最大容量。然后就可以按照背包问题…...

Linux安装jdk、mysql、并部署Springboot项目
😜作 者:是江迪呀✒️本文关键词:Linux、环境安装、JDK安装、MySQL、MySQL安装☀️每日 一言:知行合一! 文章目录 一、前言二、安装步骤2.1 安装JDK(1)创建文件夹(便于后…...

tomcat更改端口号和隐藏端口号
因为默认端口:8080不会自动隐藏,因此为了更显格调需要将其改为:80 进入tomcat的server文件 将其改为80,之后将tomcat重新启动即可 tomcat启动流程 [rootshang ~]# cd /usr/local/tomcat/apache-tomcat-8.5.92 [rootshang apache-tomcat-8.5.92]# cd b…...

生信分析Python实战练习 2 | 视频19
开源生信 Python教程 生信专用简明 Python 文字和视频教程 源码在:https://github.com/Tong-Chen/Bioinfo_course_python 目录 背景介绍 编程开篇为什么学习Python如何安装Python如何运行Python命令和脚本使用什么编辑器写Python脚本Python程序事例Python基本语法 数…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

7.4.分块查找
一.分块查找的算法思想: 1.实例: 以上述图片的顺序表为例, 该顺序表的数据元素从整体来看是乱序的,但如果把这些数据元素分成一块一块的小区间, 第一个区间[0,1]索引上的数据元素都是小于等于10的, 第二…...

【网络安全产品大调研系列】2. 体验漏洞扫描
前言 2023 年漏洞扫描服务市场规模预计为 3.06(十亿美元)。漏洞扫描服务市场行业预计将从 2024 年的 3.48(十亿美元)增长到 2032 年的 9.54(十亿美元)。预测期内漏洞扫描服务市场 CAGR(增长率&…...

什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...

【字节拥抱开源】字节团队开源视频模型 ContentV: 有限算力下的视频生成模型高效训练
本项目提出了ContentV框架,通过三项关键创新高效加速基于DiT的视频生成模型训练: 极简架构设计,最大化复用预训练图像生成模型进行视频合成系统化的多阶段训练策略,利用流匹配技术提升效率经济高效的人类反馈强化学习框架&#x…...

XXE漏洞知识
目录 1.XXE简介与危害 XML概念 XML与HTML的区别 1.pom.xml 主要作用 2.web.xml 3.mybatis 2.XXE概念与危害 案例:文件读取(需要Apache >5.4版本) 案例:内网探测(鸡肋) 案例:执行命…...