algorithm - マージソート時間が増加していることの証明

Question

本から質問があります：

(C(N+1 > C(N)マージ ソートで使用される比較の数が、すべての に対して単調に増加することを証明しますN>0)。

私は証明がとても苦手です。これを行うための手順を誰か教えてもらえますか?

Answer 1

これを行うための全体的な方法は、マージソートアルゴリズムに従って、C(N) を C(M) と C(NM) に分割することです。C(N) についても同じことを行います。C(M) が N と N+1 で同じであるか、新しい値 (おそらく C(2*M)) を古い値 (C(M)) に分割する方法が必要です。