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

[问答题]

一个长度为n的序列，若去掉其中少数k(k<<n)个记录后，序列是按关键字有序的，则称为近似有序序列。试对这种序列讨论各种简单排序方法的时间复杂度。

推荐

赞花婆

对近似有序的序列可用直接插入排序法，其时间复杂度为O(k·n），当k<<n且n很大时，将比快速排序更有效。而起泡排序和简单选择排序的时间复杂度均为O(n²)，和k无关。本题旨在提醒读者注意算法效率讨论的前提条件。

发表于 2018-03-25 09:29:38 回复(0)

提交观点

问题信息

排序

上传者：赞花婆

难度：

1条回答 0收藏 2129浏览

扫一扫，把题目装进口袋