判断题
偏易
#20479
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
归并排序算法的时间复杂度与输入是否有序无关,始终稳定为 O(n log n)。( )
答案与解析
正确答案:对
解析
归并排序无论输入数据是否有序,归并排序的时间复杂度 始终为 O(nlog?n)。这是因为:
分解阶段:将数组递归地分成两半,直到子数组长度为 1,共需 log?n 层递归。
合并阶段:每一层需要 O(n) 的时间合并两个有序子数组。
总时间复杂度:递归深度 log?n × 每层 O(n)) = O(nlog?n)。