在归并排序算法分析中，' 6n‘(6n (logn+1)= 6nlogn+6n )是什么？

Question

实现合并所需的操作数为：

：6n (logn+1)= 6nlogn+6n。

logn+1是合并排序中的层数。这里的6n是什么？

Answer 1

在粗略的合并排序的情况下:两次读取以比较两个元素，一次读取和一次写入以将较小的元素复制到工作数组，然后另一次读取和另一次写入以将元素复制回原始数组，对于每个元素总共6次存储器访问(除了边界情况，例如到达运行结束，在这种情况下，其他运行的其余部分只是复制而不进行比较)。更优化的合并排序通过交替合并的方向(如果是自下而上的合并传递)或递归级别(如果是自上而下的合并传递)来避免回写步骤，从而将6减少到4。如果一个元素适合寄存器，则在比较之后，该元素将在寄存器中，并且不需要重新读取，从而将6减少到3。

Answer 2

我不确定“6n是什么”是什么意思？如果你想知道算法的复杂度(合并排序)，它可以简化为nlog(n)。你可以忽略你问题中的系数，因为当考虑到大O复杂度时，它们可以忽略不计。在计算nlog(n) +n时，您还可以忽略n，因为它的增长速度比nlog(n)慢得多。这就给您留下了nlog(n)的复杂性。