为什么将合并排序复杂性视为o(n log n)，这不是完全的复杂性

Question

我遵循该合并排序在最坏的情况下被调用，但是实际合并每个调用的拆分参数数组的复杂性又如何呢？

应合并排序实际上是n log n *排序时间的含义或其他内容。

Answer 1

在"传统"合并排序上，每个数据都通过数据的大小加倍。第一次通过后，该文件将分为长度二的部分。第二次通过后，长四个。然后八个，十六岁等。

的大小。

有必要将分类部分的大小加倍，直到有一个包含整个文件的部分。截面大小的LG（n）二倍需要达到文件大小，并且数据的每次通过将花费时间与记录数成正比。