Complexité de l'opération de fusion dans le tri par fusion

Question

Je lis l'introduction de Cormen dans les algorithmes.
Je ne comprends pas pourquoi fusionner n/k tableaux avec k éléments dans chacun d'eux a la complexité de O(n*log(n/k)). Ce qui manque ici, c'est que nous avons n/k tableaux. Par conséquent, nous devons effectuer la fusion n/(k-1) fois chacun avec O(n) limite supérieure.
Cependant, nous avons un logarithme, donc je suppose qu'il me manque quelque chose dans ma compréhension de la complexité de fusion.

Toute aide est la bienvenue.

Answer 1

Supposons que vous ne pouvez fusionner deux tableaux avec fusion (a, b), alors vous pouvez construire un « arbre » de se confond:

a b  c  d 
    ab   cd 
     abcd 

Maintenant, il est vrai que l'utilisation de cette opération que vous faites bien n/k - 1 fusionne - mais notez que la plupart d'entre eux sont faits avec peu d'éléments, significativement moins de n éléments par tableau.

Si vous calculez soigneusement, vous obtenez:

2*(n/k)/2 * k + 2*(n/k)/4 * 2k + .... + 1*n 

Si vous faites l'algèbre, vous remarquerez que c'est en effet n*log(n/k).

---

Comme un côté non, une autre façon de faire fusionner k-way est de tenir un tas de taille n/k, et laissez-le tenir le plus petit nombre de chaque tableau, qui n'a pas été encore épuisé, et tout en réitérant - obtenir le plus petit élément dans le tas au tableau des résultats.