校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > UI专业知识 > 色彩
题目

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

A.O(log(N))

B.O(N*log(N))

C.O(N)

D.O(N^2)

解答

正确答案是 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); 是一种稳定的排序算法;

C 4条回复 评论
青梅煮酒

又搞定一个知识盲区

发表于 2022-07-23 23:00:00
0 0
雾岛残月

简单易懂,很容易理解,谢谢

发表于 2021-09-09 14:50:00
0 0
遇见

时间复杂度

插入排序 O(n^2)
冒泡排序 O(n^2)
选择排序 O(n^2)
快速排序 O(n log n)
堆排序 O(n log n)
归并排序 O(n log n)
希尔排序 O(n^1.25)

发表于 2018-10-13 10:20:54
0 0
先锋

一次归并操作的时间复杂度是O(n)
对n个元素进行排序的时间:
T(n) = 2*T(n/2) + a*n (a是常数)
= 2*(2*T(n/4)+a*n/2)+a*n
= 4*T(n/4)+2a*n
= 4*(2*T(n/8)+a*n/4)+2*a*n
= 8*T(n/8)+3*a*n
...
= 2k *T(n/2k)+k*a*n
直到 n/2k = 1 (此时 k = log2n),
T(n)= 2k *T(1)+k*a*n = 2k *T(1)+k*a*n = 2k+k*a*n
= n+a*(log2n)*n
复杂度O(nlogn)

发表于 2018-10-13 10:20:33
0 0