排序算法的时间复杂度存在下界问题
对于几种常用的排序算法,无论是归并排序、快速排序、以及更加常见的冒泡排序等,这些排序算法的时间复杂度都是大于等于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))。
相关文章:
 
排序算法的时间复杂度存在下界问题
对于几种常用的排序算法,无论是归并排序、快速排序、以及更加常见的冒泡排序等,这些排序算法的时间复杂度都是大于等于O(n*lg(n))的,而这些排序算法存在一个共同的行为,那就是这些算法在对元素进行排序的时候,都会进行…...
详解洛谷P2016 战略游戏/BZOJ0495. 树的最小点覆盖之战略游戏(贪心/树形DP)
Description Bob喜欢玩电脑游戏,特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡,城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵,使得这些士兵能了望到所有的路。 注意&…...
解决The Tomcat connector configured to listen on port 8080 failed to start
问题 启动javar报错,提示如下 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实战
文章目录 深度学习自然语言处理(NLP)模型BERT:从理论到Pytorch实战一、引言传统NLP技术概览规则和模式匹配基于统计的方法词嵌入和分布式表示循环神经网络(RNN)与长短时记忆网络(LSTM)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语⾔是结构化的程序设计语⾔,这⾥的结构指的是…...
 
C#用Array类的FindAll方法和List<T>类的Add方法按关键词在数组中检索元素并输出
目录 一、使用的方法 1. Array.FindAll(T[], Predicate) 方法 (1)定义 (2)示例 2.List类的常用方法 (1)List.Add(T) 方法 (2)List.RemoveAt(Int32) 方法 (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官网:https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢,可以使用淘宝定制的 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步进电机系列教程】
↑↑↑点击上方【目录】,查看本系列全部文章 摘要:前面章节主要介绍了bresenham直线插值运动,本节内容介绍让两个电机完成连续的直线运动,目标是画一个正五角星 一、五角星图介绍 五角星总共10条直线,10个顶点。设定左下角为原点…...
 
Elasticsearch:基本 CRUD 操作 - Python
在我之前的文章 “Elasticsearch:关于在 Python 中使用 Elasticsearch 你需要知道的一切 - 8.x”,我详细讲述了如何建立 Elasticsearch 的客户端连接。我们也详述了如何对数据的写入及一些基本操作。在今天的文章中,我们针对数据的 CRUD (cre…...
 
1992-2022年全国及31省对外开放度测算数据(含原始数据+计算结果)(无缺失)
1992-2022年全国及31省对外开放度测算数据(含原始数据计算结果)(无缺失) 1、时间:1992-2022年 2、来源:各省年鉴、国家统计局、统计公报、 3、指标:进出口总额(万美元)…...
 
JVM之GC垃圾回收
GC垃圾回收 如何判断对象可以回收 引用计数法 如果有对象引用计数加一,没有对象引用,计数减一,如果计数为零,则回收 但是如果存在循环引用,即A对象引用B对象,B对象引用A对象,会造成内存泄漏 可…...
 
自然语言学习nlp 六
https://www.bilibili.com/video/BV1UG411p7zv?p118 Delta Tuning,尤其是在自然语言处理(NLP)和机器学习领域中,通常指的是对预训练模型进行微调的一种策略。这种策略不是直接更新整个预训练模型的权重,而是仅针对模型…...
fpga 需要掌握哪些基础知识?
个人根据自己的一些心得总结一下fpga 需要掌握的基础知识,希望对你有帮助。 1、数电(必须掌握的基础),然后进阶学模电, 2、掌握HDL(verilog或VHDL)一般建议先学verilog,然后可以学…...
 
Qt未来市场洞察
跨平台开发:Qt作为一种跨平台的开发框架,具有良好的适应性和灵活性,未来将继续受到广泛应用。随着多设备和多平台应用的增加,Qt的前景在跨平台开发领域将更加广阔。 物联网应用:由于Qt对嵌入式系统和物联网应用的良好支…...
 
GPT-4模型中的token和Tokenization概念介绍
Token从字面意思上看是游戏代币,用在深度学习中的自然语言处理领域中时,代表着输入文字序列的“代币化”。那么海量语料中的文字序列,就可以转化为海量的代币,用来训练我们的模型。这样我们就能够理解“用于GPT-4训练的token数量大…...
宽字节注入漏洞原理以及修复方法
漏洞名称:宽字节注入 漏洞描述: 宽字节注入是相对于单字节注入而言的,该注入跟HTML页面编码无关,宽字节注入常见于mysql中,GB2312、GBK、GB18030、BIG5、Shift_JIS等这些都是常说的宽字节,实际上只有两字节。宽字节带来的安全问…...
 
【Linux】SystemV IPC
进程间通信 一、SystemV 共享内存1. 共享内存原理2. 系统调用接口(1)创建共享内存(2)形成 key(3)测试接口(4)关联进程(5)取消关联(6)释…...
iview 页面中判断溢出才使用Tooltip组件
使用方法 <TextTooltip :content"contentValue"></TextTooltip> 给Tooltip再包装一下 <template><Tooltip transfer :content"content" :theme"theme" :disabled"!showTooltip" :max-width"300" :p…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
React hook之useRef
React useRef 详解 useRef 是 React 提供的一个 Hook,用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途,下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
 
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
 
初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
 
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
