algorithm - 证明归并排序时间在增加

Question

我有一个书上的问题：

证明归并排序使用的比较次数(C(N+1 > C(N)对 all单调递增N>0)。

我真的不擅长打样。任何人都可以引导我完成如何完成此操作的步骤吗？

Answer 1

这样做的总体方法是，根据您的合并排序算法将 C(N) 分解为 C(M) 和 C(NM)。对 C(N) 做同样的事情。对于 N 和 N+1，要么有重叠 C(M) 相同，要么应该有某种方法将新值（可能是 C(2*M)）分解为旧值（C(M)）。