Intuitivement arbre évasement (arbres d'équilibrage auto)

Question

Je lis les bases des arbres ébrasés. Le coût amorti d'une opération est O (log n) opérations sur n. Une certaine idée de base est rude que lorsque vous accédez à un nœud, vous évasement il dire que vous prenez à la racine prochaine fois que cela est rapidement accessible et aussi si le nœud était profond, il améliore l'équilibre-ness de l'arbre.

Je ne comprends pas comment l'arbre peut effectuer O amorti (log n) pour cette entrée échantillon:

Dites un arbre de nœuds n est déjà construit. Mes prochaines opérations n sont n lit. J'accéder à un mot profond de nœud en profondeur n. Cela prend O (n). Certes, après cet accès, l'arbre deviendra équilibré. Mais dire chaque fois que j'accéder au nœud le plus profond courant. Ce ne sera jamais inférieur à O (log n). alors comment nous pouvons jamais compenser le premier O coûteux (n) exploitation et ramener le coût amorti de chaque lecture comme O (log n)?

Merci.

Answer 1

En supposant que votre analyse est correcte et les opérations sont O(log(n)) par accès et O(n) la première fois ...

Si vous accédez toujours l'élément de plus basse (en utilisant une sorte d'oracle pire des cas), une séquence d'accès de a prendra O(a*log(n) + n). Et ainsi le coût amorti par opération est O((a*log(n) + n)/a) = O(log(n) + n/a) ou juste O(log(n)) que le nombre d'accès grossit.

Ceci est la définition de la performance moyenne cas asymptotique / temps / espace, aussi appelé « performance amorti / espace / temps ». Vous pensez par hasard qu'une seule étape de O(n), toutes les étapes sont au moins O(n); une telle mesure est qu'une quantité constante de travail à long terme; le O(...) se cache ce qui se passe vraiment, qui prend la limite de [total amount of work] / [queries] = [average ("amortized") work per query].

Ce ne sera jamais inférieur à O (log n).

Il doit être pour obtenir une performance moyenne O(log n). Pour obtenir l'intuition, le site Web suivant peut être bon: http: // utilisateurs .informatik.uni-halle.de / ~ jopsi / dinf504 / chap4.shtml spécifiquement l'image