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

排序算法的时间复杂度存在下界问题

对于几种常用的排序算法,无论是归并排序、快速排序、以及更加常见的冒泡排序等,这些排序算法的时间复杂度都是大于等于O(n*lg(n))的,而这些排序算法存在一个共同的行为,那就是这些算法在对元素进行排序的时候,都会进行同一个操作,也就是对数组中取出文件,然后会对取出来的这两个元素进行相互比较。

而针对这个,我们是可以从理论上进行证明,也就是任何的排序算法,只要这个排序算法会存在一个取出元素的动作,那就会存在以上的结论,时间复杂度大于等于O(n*lg(n)),例如在冒泡排序中,依次取出 两个元素,对这个元素进行比较大小,然后调整被比较元素的位置。在归并排序中,将数组分为两个子数组进行排序,然后依次从两个排好序的数组中取出元素进行比较以便将他们合并成为一个元素。在堆排序中,每次往堆中增加一个新元素的时候,它都必须与父节点比较,然后根据比较之后的大小来和父节点进行位置的调换。而在快速排序中,选中一个pivot元素的话,其他元素就需要与该元素进行比较,以此来进行位置调换。

只要将两个元素进行比较,那必然会执行三个测试,也即是a<b,a>b,a=b的行为,由此会得出两个元素的相对位置,如果将等于这个行为与其中一个行为合并之后,该测试行为会被简化为两个行为,也就是a<=b或者是a>b,也就是说,元素比较的的结果会产生两个可能,大于或者小于等于,类比为比较行为当成是一个父节点,可能会产生的两个孩子节点:

添加图片注释,不超过 140 字(可选)

而如果将排序算法中每一次的比较用图表示,那么就会得到一个二叉树结构,冒泡排序的结果:

添加图片注释,不超过 140 字(可选)

添加图片注释,不超过 140 字(可选)

将所有可能性展开之后,就会得到如上图所示的二叉树模型,改模型也叫作决策树模型,在叶子节点中列出了元素排列的所有可能性,因此数组排序之后,其元素的排列一定属于叶子节点所表示的某一种情况。

由此基于元素比较的排序算法,本质上是从顶层根节点开始,沿着左边或者右边的某个分支一直走到底层某个节点。

分析叶子节点的数量与高度的关系,由于一个父节点可以衍生出来两个孩子节点,因此每下降一层的话,节点的数量就是上一层的两倍,如果决策树的高度使用h表示的话,就可以得出叶子节点数量是最多是2的h次方个。

每个节点对应元素的一种排列方式的话,那如果数组会有n个节点,那么节点排列的可能性总共有n的阶乘中,也就是说,决策树底层会有n的阶乘个叶子结点,由于决策树底层叶子结点对应的元素排好序之后的排列,依次决策树的叶子节点必须大于等于n的阶乘。

从这里就可以得出结论,时间复杂度大于等于O(n*lg(n))。

相关文章:

排序算法的时间复杂度存在下界问题

对于几种常用的排序算法&#xff0c;无论是归并排序、快速排序、以及更加常见的冒泡排序等&#xff0c;这些排序算法的时间复杂度都是大于等于O(n*lg(n))的&#xff0c;而这些排序算法存在一个共同的行为&#xff0c;那就是这些算法在对元素进行排序的时候&#xff0c;都会进行…...

详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)

Description Bob喜欢玩电脑游戏&#xff0c;特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡&#xff0c;城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵&#xff0c;使得这些士兵能了望到所有的路。 注意&…...

解决The Tomcat connector configured to listen on port 8080 failed to start

问题 启动javar报错&#xff0c;提示如下 Description: The Tomcat connector configured to listen on port 8080 failed to start. The port may already be in use or the connector may be misconfigured. Action: Verify the connector’s configuration, identify a…...

深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战

文章目录 深度学习自然语言处理&#xff08;NLP&#xff09;模型BERT&#xff1a;从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络&#xff08;RNN&#xff09;与长短时记忆网络&#xff08;LSTM&#xff09;Transform…...

C语言的循环结构

目录 前言 1.三种循环语句 1.while循环 2.for循环 2.1缺少表达式的情况 3.do while循环 2.break语句和continue语句 2.1在while循环中 2.2在for循环中 2.3在do while 循环中 3.循环的嵌套 4.go to语句 前言 C语⾔是结构化的程序设计语⾔&#xff0c;这⾥的结构指的是…...

C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出

目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;示例 2.List类的常用方法 &#xff08;1&#xff09;List.Add(T) 方法 &#xff08;2&#xff09;List.RemoveAt(Int32) 方法 &#xff08;3&…...

【前后端接口AES+RSA混合加解密详解(vue+SpringBoot)附完整源码】

前后端接口AES+RSA混合加解密详解(vue+SpringBoot) 前后端接口AES+RSA混合加解密一、AES加密原理和为什么不使用AES加密二、RSA加密原理和为什么不使用rsa加密三、AES和RSA混合加密的原理四、代码样例前端1. 请求增加加密标识2. 前端加密工具类3.前端axios请求统一封装,和返…...

React环境配置

1.安装Node.js Node.js官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…...

Pandas 数据处理-排序与排名的深度探索【第69篇—python:文本数据处理】

文章目录 Pandas 数据处理-排序与排名的深度探索1. sort_index方法2. sort_values方法3. rank方法4. 多列排序5. 排名方法的参数详解6. 处理重复值7. 对索引进行排名8. 多级索引排序与排名9. 更高级的排序自定义10. 性能优化技巧10.1 使用nsmallest和nlargest10.2 使用sort_val…...

第8节、双电机多段直线运动【51单片机+L298N步进电机系列教程】

↑↑↑点击上方【目录】&#xff0c;查看本系列全部文章 摘要&#xff1a;前面章节主要介绍了bresenham直线插值运动&#xff0c;本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线&#xff0c;10个顶点。设定左下角为原点…...

Elasticsearch:基本 CRUD 操作 - Python

在我之前的文章 “Elasticsearch&#xff1a;关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x”&#xff0c;我详细讲述了如何建立 Elasticsearch 的客户端连接。我们也详述了如何对数据的写入及一些基本操作。在今天的文章中&#xff0c;我们针对数据的 CRUD (cre…...

1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)

1992-2022年全国及31省对外开放度测算数据&#xff08;含原始数据计算结果&#xff09;&#xff08;无缺失&#xff09; 1、时间&#xff1a;1992-2022年 2、来源&#xff1a;各省年鉴、国家统计局、统计公报、 3、指标&#xff1a;进出口总额&#xff08;万美元&#xff09…...

JVM之GC垃圾回收

GC垃圾回收 如何判断对象可以回收 引用计数法 如果有对象引用计数加一&#xff0c;没有对象引用&#xff0c;计数减一&#xff0c;如果计数为零&#xff0c;则回收 但是如果存在循环引用&#xff0c;即A对象引用B对象&#xff0c;B对象引用A对象&#xff0c;会造成内存泄漏 可…...

自然语言学习nlp 六

https://www.bilibili.com/video/BV1UG411p7zv?p118 Delta Tuning&#xff0c;尤其是在自然语言处理&#xff08;NLP&#xff09;和机器学习领域中&#xff0c;通常指的是对预训练模型进行微调的一种策略。这种策略不是直接更新整个预训练模型的权重&#xff0c;而是仅针对模型…...

fpga 需要掌握哪些基础知识?

个人根据自己的一些心得总结一下fpga 需要掌握的基础知识&#xff0c;希望对你有帮助。 1、数电&#xff08;必须掌握的基础&#xff09;&#xff0c;然后进阶学模电&#xff0c; 2、掌握HDL&#xff08;verilog或VHDL&#xff09;一般建议先学verilog&#xff0c;然后可以学…...

Qt未来市场洞察

跨平台开发&#xff1a;Qt作为一种跨平台的开发框架&#xff0c;具有良好的适应性和灵活性&#xff0c;未来将继续受到广泛应用。随着多设备和多平台应用的增加&#xff0c;Qt的前景在跨平台开发领域将更加广阔。 物联网应用&#xff1a;由于Qt对嵌入式系统和物联网应用的良好支…...

GPT-4模型中的token和Tokenization概念介绍

Token从字面意思上看是游戏代币&#xff0c;用在深度学习中的自然语言处理领域中时&#xff0c;代表着输入文字序列的“代币化”。那么海量语料中的文字序列&#xff0c;就可以转化为海量的代币&#xff0c;用来训练我们的模型。这样我们就能够理解“用于GPT-4训练的token数量大…...

宽字节注入漏洞原理以及修复方法

漏洞名称:宽字节注入 漏洞描述: 宽字节注入是相对于单字节注入而言的&#xff0c;该注入跟HTML页面编码无关&#xff0c;宽字节注入常见于mysql中&#xff0c;GB2312、GBK、GB18030、BIG5、Shift_JIS等这些都是常说的宽字节&#xff0c;实际上只有两字节。宽字节带来的安全问…...

【Linux】SystemV IPC

进程间通信 一、SystemV 共享内存1. 共享内存原理2. 系统调用接口&#xff08;1&#xff09;创建共享内存&#xff08;2&#xff09;形成 key&#xff08;3&#xff09;测试接口&#xff08;4&#xff09;关联进程&#xff08;5&#xff09;取消关联&#xff08;6&#xff09;释…...

iview 页面中判断溢出才使用Tooltip组件

使用方法 <TextTooltip :content"contentValue"></TextTooltip> 给Tooltip再包装一下 <template><Tooltip transfer :content"content" :theme"theme" :disabled"!showTooltip" :max-width"300" :p…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...