我目前正在尝试解决上述重复关系，但是在尝试破译模式并将其重写为总和时遇到了麻烦。有人可以帮我吗？
k> =0。T（n <= 2）= 1。
此递归关系是从我编写的算法中获得的，该算法是从已排序k个数组（这意味着第k个元素按排序顺序）中获得单个排序数组。该算法最多运行k次。每次k减少一个，第k个元素添加到另一个数组。最后，使用合并排序中的合并（n次）合并每个数组。递归调用此算法，直到k = 0，这意味着我们找到了每个已排序的子数组。
我感觉这是O（k * n），但我不确定。
可能需要注意的是
n-n / k =（（k-1）/ k）n，
因此，您的递归关系表示n在每一步中均以（k-1）/ k的因子进行几何衰减。要查看完成了多少工作，令a =（k-1）/ k。然后，已完成的工作的上限是
n + an + a 2 n + a 3 n + ...
= n /（1-a）
= n /（1 / k）
= nk。
所以您的总工作量为O（nk）。
[注意，我尚未检查您的重复关系是否与您的代码匹配-我只是在这里显示数学。 ：-）