在最坏情况下,MergeSort的时间复杂度为O(nlogn),其中n是待排序数组的长度。MergeSort通过将数组分成两个子数组并对其进行递归排序,然后合并这两个已排序的子数组,以达到整个数组有序的目的。由于每次递归调用都会把数组分成两半,因此整个过程的时间复杂度是O(logn)。在每次合并操作中需要比较和移动n个元素,所以时间复杂度是O(n)。因此,总的时间复杂度是O(nlogn)。
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
推荐阅读:spfa算法的时间复杂度是多少