对于近似有序序列（即除掉少数K个元素后是有序序列且K<<n），试分析直接插入排序，冒牌排序和简单选择排序的时间复杂度
2024-08-29 19:40:29
学弟问的一道数据结构的题，关于一些排序算法的时间复杂度。
针对近似有序序列，
①当使用直接插入排序时，其基本操作为数组中元素的移动。最好情况下，待排序列有序，无需移动，此时时间复杂度为O（n），
当为近似有序序列是，其基本操作执行的次数是K次当前循环的最大值的和，即时间复杂度为O（k.n）由于k远小于n，
综合考虑直接插入排序的时间复杂度为O（n）
②当使用冒泡排序时，默认为普通冒泡排序，其基本操作为元素间比较的次数，因此无论
是否是近似有序，时间复杂度均为O（n^2）
③当使用简单排序时，其基本操作也为元素间的比较，与待排序列状态无关，即第i次的
比较次数为n-i,时间复杂度为O（n^2）
综上，若当前序列为近似有序序列时，直接插入排序效率最高。
最新文章
- Trigger和ViewStateManager的具体比较
- Android Hook 借助Xposed
- QT中的C/S通信问题：关于服务器端readyread()信号不发射
- okhttp 基本介绍
- 河内塔(hanoi)
- OpenStack securityGroup rule Set
- BrowserSync使用
- 分布式唯一ID生成方案是什么样的？（转）
- Docker(五)：Docker 三剑客之 Docker Machine
- c# 读取txt方法
- angularjs探秘<二>表达式、指令、数据绑定
- 流程图工具Visual Paradigm for UML
- 52.tableViewCell重用机制避免重复显示问题
- Python2.7-fileinput
- dokuwiki工具栏添加换行回车快捷键与按钮
- 51单片机和Arduino—闪烁灯实现
- CreateThread与_beginthreadex本质区别
- JS - 二叉树算法实现与遍历 (更新中...)
- python面试题（转）
- Metasploit拿Shell