试题
考点

数据结构-排序-归并排序

面5笔5

归并排序的时间复杂度()

A.O(log(N))

B.O(N*log(N))

C.O(N)

D.O(N^2)

前往“校招VIP”小程序,刷题更快
最新校招难题刷题,快来进刷题群吧
解答

正确答案是 B

交换排序

快速排序法: 当数据几乎有序是:每次取的基准都是最大或者最下时;快速排序法的查找时间是最慢的为 O(n*2), 每次都是去中间的位置时;无序时快速排序才是最快的 O(nlogn); 平均时间复杂度为 O(nlogn);

冒泡排序: 初始状态有序且是升序时冒泡排序的事件复杂度为 O(n-1); 仅仅比较 n-1 次;当初始序列为降序是 O(n(n-1)/2) 即为O(n*2); 初始序列无序时:平均的时间复杂度为 O(n*2);

插入排序算法:

直接插入排序: 当初始序列为正序时为 O(n), 初始序列为反序是 O(n*2); 平均时间复杂度为 O(n*2)

希尔排序法: Shell 排序的时间性能优于直接插入排序;平均时间复杂度为 O(n*1.25), 是一种不稳定的的排序算法;分组排序;

选择排序:

堆排序法 的最坏时间复杂度为 O(nlogn) 接近平均时间复杂度;不稳定的排序算法,就地排序,辅助空间为 O(1);

直接选择排序 和文件的初始状态无关:都为 O(n*2);

归并算法:

归并排序算法:无论最好还是最坏均为: O(nlgn); 空间复杂度为 O(n); 是一种稳定的排序算法;

评论

青梅煮酒

2022-07-23 23:00:00

0 0

雾岛残月

2021-09-09 14:50:00

0 0

遇见

2018-10-13 10:20:54

时间复杂度

平均时间复杂度
插入排序 O(n^2)
冒泡排序 O(n^2)
选择排序 O(n^2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
基数排序 O(n)
希尔排序 O(n^1.25)

0 0

加载更多