判断题 偏易
#20479

归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )

未登录也能判分,登录后才会记录
答案与解析
正确答案:对
解析

归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:

分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。

合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。

总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。