因为我写不出递回式,所以用iterative分析:
1 因为merge的过程中只要其中一个run为空就会马上return 所以不管是n/k跟n/k做merge
或是3n/k与n/k做merge应该都是花O(n/k)的时间
2 因为他是依序往后merge所以总共会执行k回合
这样分析下来应该是k*n/k也就是O(n)吧?
为什么答案是给n*k?话说题目说的following algorithm是...?(104交大资演)
如果每次merge都要做最大run原是个数的时间才有机会被bound在n*k吧?