为什么归并排序最坏情况下的运行时间为O（n log n）的？ [英] Why is merge sort worst case run time O (n log n)?

问题描述

有人能向我解释，在简单的英语或一个简单的方法来解释它？

Can someone explain to me in simple English or an easy way to explain it?

推荐答案

在传统的归并排序，每次通过数据加倍排序小节的大小。第一遍之后，该文件将被分类到长度的两个部分。第二遍后，长度为4。然后8，16，等等直至文件的大小。

On a "traditional" merge sort, each pass through the data doubles the size of the sorted subsections. After the first pass, the file will be sorted into sections of length two. After the second pass, length four. Then eight, sixteen, etc. up to the size of the file.

这是需要保持排序节的规模扩大一倍，直到有一个部分包括整个文件。这将需要lg的截面尺寸（N）的倍增到达文件的大小，以及数据的每遍需要时间成比例的记录数

It's necessary to keep doubling the size of the sorted sections until there's one section comprising the whole file. It will take lg(N) doublings of the section size to reach the file size, and each pass of the data will take time proportional to the number of records.

这篇关于为什么归并排序最坏情况下的运行时间为O（n log n）的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！