算法-关于时间复杂度的证明

Question

现有n个元素要排序，输入序列含n个数字，被分成n/k组，每组有k个数，假定共m组，第i组中数字的值都小于第i+1组而小于i-1组，即只需对组内数字进行排序即可，证明此排序问题中时间下界为nlgk，注意，不能将每个子序列的时间下界简单叠加；求明确的证明过程

Answer 1

可能的顺序一共有(k!)^m种，每次比较可以有两个分支，因此决策树至少有log2((k!)^m)层，即m*log(k!) = O(mklogk) = O(nlogk)