二路归并排序时间复杂度

Question

如题所述

Answer 1

二路归并排序时间复杂度是O（nlogn）。

对于每一层来说，在合并所有子区间的过程中，n个元素都会被操作一次，所以每一层的时间复杂度都是O（n）。而之前说过，归并排序划分子区间，将子区间划分为只剩1个元素，需要划分logn次。每一层的时间复杂度为O（n），共有logn层，所以归并排序的时间复杂度就是O（nlogn）

归并排序是一种借助”归并“进行排序的方法。归并的含义是将两个或两个以上的有序序列归并为一个有序序列的过程。归并排序的主要思想是：将若干有序序列逐步归并，最终归并为一个有序序列。

其中最常见的是二路归并排序。二路归并排序是一种稳定的排序方法，其基本思想是：将若干个有序序列两两归并，直到形成一个有序序列为止。方法如下：将一个长度为n的无序序列看作是n个长度为1的有序序列的集合。然后两两归并，直到整个序列有序。

在归并的过程中，可能会破坏原序列的有序性，所以需要一个新的数组在存储归并后的结果。一次归并的算法是从开始同时遍历两个序列，将较小的值放入结果序列中，直到遍历结束，成为一个有序序列。