fusionner trier hauteur de l'arbre récursif

Question

Je suis en train d'apprendre à propos de l'arbre de la récurrence et d'essayer de comprendre comment la hauteur de l'arbre est log b de n où n = 2 et on a 10 éléments comme taille d'entrée. Je travaille avec Merge sorte.

Le nombre de fois que la répartition se fait est la hauteur de l'arbre pour autant que je compris, et le nombre de niveaux dans l'arbre en hauteur + 1.

Mais si vous prenez (pour le tri de fusion) log2 de 10 vous obtenez 1, où si vous dessinez l'arbre vous obtenez au moins 2 fois que la récursivité se produit.

Où est-ce que je me suis trompé? (J'espère que j'ai du sens ici)

NOTE: Je fais un autoformation, ce n'est pas des devoirs!

Answer 1

log (10) = 3,321928094887362 ...

Dans tous les cas, la profondeur d'appel récursif est O(log(n)), ce qui signifie essentiellement "de l'ordre de log (n)". La profondeur d'appel réelle pour un algorithme O (log (n)) peut être k*log(n)+c, ou même k*log(n)+ α (n)/log(log(n))+c.