$ \ Phi_1= 1 $ ou $ \ phi_1= 2 $ pour le texte dynamique $ \ Text {insert de table} $, où $ \ phi_i $ est la fonction potentielle après $ i $ ème opération, conformément à CRRS

Question

Ce qui suit vient de la section Tables dynamiques , Introduction aux algorithmes par Cormen. ET. al.

---

Dans le pseudocode suivant, nous supposons que $ t $ est un objet représentant la table. Le champ $ table [t] $ contient un pointeur sur le bloc de stockage représentant la table. Le champ $ num [t] $ contient le nombre d'éléments dans la table et le champ $ Tailled $ [T] $ est le nombre total de machines à sous dans la table. Initialement, la table est vide: $ num [t]= taille [t]= 0 $ .

.

$ \ texte {insert de table (t, x)} $

1 $ \ quad \ texte {si taille $ Taille [t]= 0 $} $

2 \ quad \ quad \ text \ text {puis allouer $ Table [t] $ avec 1 $ Slot} $

3 \ quad \ quadze taille [t] \ raquetarrow 1 $

4 \ quad \ texte {si} num [t]= taille [t] $

$ 5 \ quad \ quad \ text {TROUVEZ allocation $ nouvelle {\ Text {-}} Tableau $ avec $ 2 \ CDOT Taille [t] $ Slots} $

6 \ quad \ quad \ quad \ quad \ text {insérez tous les éléments en $ Table [T] $ en $ nouveau {\ texte {-}} $

7 \ quad \ quad \ quad \ quad \ text {gratuit $ table [t] $} $

8 \ quad \ quad \ quad \ quad \ Table [T] \ WASTARROW Nouveau {\ Text {-}} Tablear $

9 \ quad \ quad \ quad \ quad \ Taille [T] \ Taille de la Cdot 2 \ CDOT [T] $

10 $ \ quad \ texte {insérer $ x $ en $ table [t] $} $

11 $ \ Quad num [t] \ Num de gauche [T] + 1 $

pour l'analyse amortise pour la séquence d'une séquence de $ N $ $ \ texte {insert de table} $ La fonction potentielle qu'ils choisissent est la suivante,

$$ \ phi (t)= 2.num [t] -Size [t] $$

Pour analyser le coût amorti de la I $ I $ TH $ \ TEXTE {INSERT TABLE-INSERT} $ Opération, nous laissons $ NUM_I $ désignent le nombre d'éléments stockés dans le tableau après la $ i $ ème opération, $ taille_i $ désigne la taille totale de la table après la $ i $ e opération, et $ \ phi_i $ désigne le potentiel après la $ i $ ème opération.

Initialement, nous avons $ num_0= 0, taille_0= 0 $ et $ \ hi_0= 0 $ .

Si la $ I $ I $ TH Fonctionnement de l'insertion de table ne déclenche pas une expansion, alors nous avons $ TIZE_I= Taille_ {ii} $ et $ num_i= num_ {i-1} +1 $ , le coût amorti de l'opération est $ \ widehat {c_i} $ est le coût amorti et $ c_i $ est le coût total.

$$ \ widehat {c_i}= c_i + \ phi_- \ phi_ {i-1}= 3 \ texte {(Détails non affichés)} $$ < / p>

Si la $ I $ TH Opération déclenche une expansion, puis nous avons $ TIZE_I= 2. taille_ {i-1} $ et $ Taille_ {i-1}= num_ {i-1}= num_i -1 $ encore, < / p>

$$ \ widehat {c_i}= c_i + \ phi_- \ phi_ {i-1}= 3 \ texte {(Détails non affichés)} $$ < / p>

---

maintenant le problème est qu'ils ne font pas de calculs pour $ \ widehat {c_1} $ , la situation de la première insertion d'un L'élément du tableau (ligne 1,2,3,10,11 de code n'est exécuté que).

Dans cette situation, le coût $ C_1= 1 $ , $ \ phi_0= 0 $ et $ NUM_1= Taille_1= 1 \ implique \ phi_1= 2.1-1= 1 $

Nous voyons que $ \ phi_1= 1 \ tag 1 $

donc, $$ \ widehat {c_1}= c_1 + \ phi_1- \ phi_0= 2 $$

Mais le texte dit que le coût amorti est 3 $ (je pense qu'ils auraient dû dire que le coût amorti est au plus $ 3 $ , de ce que je peux comprendre)

En outre dans l'intrigue ci-dessous,

Le texte représente graphiquement la $ \ phi_1= 2 $ quel type de contradiction contredit

er "> $ (1) $ , mais selon le graphique si nous supposons $ \ phi_1= 2 $ alors $ \ widehat {c_i}= 3, \ Forall i $

Je ne reçois pas tout à fait où je fais la confection.

Answer 1

Vous avez attrapé une instance de l'erreur particulière d'intercommunication dans ce manuel populaire dont nous ne le mentionnerons plus.

Pour répéter, il est correct que "le coût $ c_1= 1 $ , $ \ hi_0= 0 $ < / span> "," $ num_1= Taille_1= 1 $ $ \ implique $ Conteneur mathématique "> $ \ phi_1= 2 \ CDOT1-1= 1 $ " et " $ \ chapeau {c_1}= "Conteneur mathématique"> $ C_1 + \ phi_1- \ phi_0 $ $= 2 $ ". Il est incorrect d'indiquer que $ \ widehat c_i= 3 $ pour tous $ i $

la première $ \ text {t} \ scriptsize {\ texte {capable}} \ text \ text {-i} \ scriptsize \ texte {nsert} $ L'opération est en effet très spéciale. Il n'est pas considéré comme une expansion, un événement défini comme "dans lequel les lignes 5-9 sont exécutées". Cependant, il ne maintient pas $ taille_i= taille_ {i-1} $ , non plus. Donc, ni le calcul de $ \ widehat {c_i} $ dans le manuel est adapté à $ \ widehat {c_1} $ .

Cette erreur est confuse étant donné que nous avons tendance à faire confiance à un manuel exemplaire où une grande attention a été portée au détail et à l'exactitude.

D'autre part, cette erreur n'est pas très importante car, comme vous l'avez noté, il est toujours considéré que "le coût amorti est au plus 3".

Au fait, si vous regardez de plus près le chiffre à la fin de la question, il montre le potentiel à la fin de la première $ \ text {t} \ scriptsize { \ texte {capable}} \ petit \ texte {-i} \ scriptsize \ texte {nsert} {nsert} $ opération, $ \ phi_1= 1 $ , Valeur correcte.