Algs4-2.2.7证明归并排序的比较次数是单调递增的

2.2.7证明归并排序的比较次数是单调递增的(即对于N>0,C(N+1)>C(N))。
证：由命题F得出数组长度为N时比较次数为C(N)=NlgN,当数组长度为N+1时比较次数为C(N+1)=NlgN，由于N+1>N,所以有lg(N+1)>lg(N),所以有C(N+1)=(N+1)lg(N+1)>NlgN=C(N)。
参考资料命题F:
图片

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/longjin2018/p/9860084.html