首页 > 试题广场 >

一个长度为n的序列，若去掉其中少数k(kn)个记录后，序

[问答题]
一个长度为n的序列，若去掉其中少数k(k<<n)个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。
添加回答
推荐
赞花婆头像 赞花婆
对近似有序的序列可用直接插入排序法，其时间复杂度为O(k·n），当k<<n且n很大时，将比快速排序更有效。而起泡排序和简单选择排序的时间复杂度均为O(n2)，和k无关。本题旨在提醒读者注意算法效率讨论的前提条件。
发表于 2018-03-25 09:29:38 回复(0)
提交观点

问题信息

排序
上传者：赞花婆
难度：
1条回答 2105浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号