Durée d'ajout de N éléments dans un arbre AVL vide

Question

La formule pour "nœuds minimum pour un arbre avl en hauteur h" est récursive: n (0) = 1, n (1) = 2 n (h) = 1 + n (h-1) + n (h-2)

d'autre part, je trouve cela dans Internet pour expliquer la complexité de l'ajout d'éléments de N à un arbre AVL vide:

Well, imagine the tree being built. 
One by one, the elements go through the tree nodes, and chose their abode by   taking either a left or a right. The tree balances itself every time the heights are too skewed. 

Of course, the cost of balancing the tree is an O(1) operation, so I do not consider that in the complexity analysis. 

Complexity: log(1)+log(2)+log(3)+....+log(n) 
=log(n!) 
=O(nlogn-n+O(log(n))) 
=O(nlogn) 

Mais voici ce que je ne comprends pas, pourquoi est le journal de calcul (n!) Si PAS chaque fois que j'ajoute un élément la hauteur augmente? puisque la formule récursive présentée s'applique pour un grand N, la hauteur avl n'augmente qu'après beaucoup d'éléments, donc asymptotiquement ne devrait-elle pas être meilleure que log (n!)?

Aussi, quel est le pire des cas pour cela? Y at-il un pire cas et le meilleur des cas dans cette situation de complexité? Par exemple, supposons que j'ai des éléments N spécifiques que j'ajoute, pourrait-il y avoir un meilleur temps d'exécution pour différentes courses? Ou puis-je dire qu'il est connu d'avance où chaque élément va être ajouté de sorte que le temps de course est limité?

Answer 1

Simpler Limite supérieure Explaination

Si vous avez n éléments, la plupart du temps un insert prendra est log (n). Si nous supposons que le pire cas insère le temps pour tous les éléments n, alors vous obtenez O(n*log(n)) sans l'explication complexe.

Une autre façon de regarder est:

log (1) + log (2) + log (3) + ... + log (n) < n * log (n) = log (n) + log (n) + ... + log (n)