Recherche équilibrée Arbre de requête, analyse asymptotique

Question

La situation est la suivante: -

Nous avons n nombre et nous avons l'impression -les dans l'ordre. Nous avons accès à structure de données de dictionnaire équilibré, qui soutient la serach des opérations, insérer, supprimer, minimum, maximum chaque en O (log n).

Nous voulons récupérer les numéros dans l'ordre trié dans O (n log n) en utilisant que l'insert et dans l'ordre traversal.

La réponse à cette question est: -

Sort() 
    initialize(t) 
    while(not EOF) 
    read(x) 
    insert(x,t); 
    Traverse(t); 

Maintenant, la requête est si nous lisons les éléments dans le temps « n », puis parcourir les éléments dans « n log » (dans l'ordre traversal) temps ,, alors le temps total pour cet algorithme (n + logn) temps, selon moi .. S'il vous plaît expliquer le suivi de cet algorithme pour le calcul du temps .. Comment ça va trier la liste en O (n log n) temps ??

Merci.

Answer 1

Chaque insert est O(log n). Vous faites n inserts, de sorte que donne n * O(log n) = O(n log n) complexité temporelle asymptotique. L'arbre est traversant O(n), car il y a n nœuds. Cela ajoute à O(n + n log n) qui diffère de O(n log n) par une constante, de sorte que la complexité asymptotique finale est O(n log n) ..

puis parcourir les éléments « log n

Traversal est O(n), pas O(log n). une insertion est O(log n) et que vous faites n ces insertions.