时间复杂度o(nlogn)的算法是什么？

Question

如题所述

Answer 1

时间复杂度o(nlogn)的算法是采用“分治思想”，将要排序的数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排序好的两部分合并在一起，这样数组就有序。

每次划分区域都选择中间点进行划分，所以递归公式可以写成：T(n) = T(n/2) + T(n/2) + n， T(1) = C(常数)    //每次合并都要调用Merge()函数，时间复杂度为O(n)，等价T(n) = 2kT(n/2k) + k * n， 递归的最终状态为T(1)即n/2k = 1，所以k = log2n。

原理分析：

1、运用了分治的思想。选取分区值，将待排序列分为两个前后两部分，前部分数据元素的值小于等于分区值，后部分的数据元素的值大于等于分区值；继续对前后两部分分别进行分区，直到分区大小为1。

2、交换操作的执行次数可以由时间复杂度分析过程得出，Merge()中总的交换次数为n * logn，因为不管两个子序列的大小，子序列中的各个元素都会先放入临时数组temp中，再重新放回原序列；比较操作的次数小于等于交换操作次数，最大交换次数为n * logn。