题目内容
(请给出正确答案)
[单选题]
若需要时间复杂度在O(nlog2n)内,对整数数组进行排序,且要求排序方法是稳定的,则可选择的排序方法是()。
A.快速排序
B.归并排序
C.堆排序
D.直接插入排序
查看答案
如果结果不匹配,请 联系老师 获取答案
A.快速排序
B.归并排序
C.堆排序
D.直接插入排序
已知有实现同一功能的两个算法,其时间复杂度分别为O(2n)和O(n10),假设计算机可连续运算的时间为107秒(100多天),又每秒可执行基本操作(根据这些操作来估算算法时间复杂度)105次,试问在此条件下,这两个算法可解问题的规模(即n值的范围)各为多少?哪个算法更适宜?请说明理由。
A.O(1)
B.O(m+n)
C.O(log2mn)
D.O(m*n)
A.空间复杂度为O(1)是指算法只占用一个临时存储单元
B.时间复杂度通常是指最坏情况下的时间复杂度
C.所用编程语言和输入数据都相同时,2个算法分别在同一台计算机上运行,花费时间较长的算法可能具有更低的时间复杂度
D.同一个算法,分别用编译型语言和解释型语言编写为程序,后者运行耗时可能更少
a)试按照以上思路,实现一个排序算法:
b)你的这一算法,时间和空间复杂度各是多少?
c)改进你的算法,使之能够在O(n+M)时间内对来自[0,M)范围内的n个整数进行排序,且使用的辅助空间不超过O(M)。