Coût amorti de l'insertion / retrait sur le tas min
J'ai récemment rencontré une question d'entrevue. aucune information supplémentaire n'est remise en question (peut-être que l'implémentation par défaut devrait être utilisée ...)
n séquences arbitraires d'opérations d'insertion et de suppression sur un tas min vide (l' emplacement de l'élément de suppression est connu ) a un coût amorti de:
A) insérer O (1), retirer O (log n)
B) insérer O (log n), retirer O (1)
L'option ( B ) est correcte.
Je suis surpris quand je vois la feuille de réponses. Je sais que c'est délicat, peut-être un tas vide, peut-être connaître l'emplacement des éléments à supprimer, ... je ne sais pas pourquoi (A) est faux? Pourquoi (B) est-il vrai?
Réponses
Lorsque vous affectez des coûts amortis à des opérations sur une structure de données, vous devez vous assurer que, pour toute séquence d'opérations effectuées, la somme des coûts amortis est toujours au moins aussi élevée que la somme des coûts réels de ces opérations.
Prenons donc l'option 1, qui attribue un coût amorti de O (1) aux insertions et un coût amorti de O (log n) aux suppressions. La question que nous devons nous poser est la suivante: est-il vrai que pour toute séquence d'opérations sur un tas binaire vide, le coût réel de ces opérations est plafonné par le coût amorti de ces opérations? Et dans ce cas, la réponse est non. Imaginez que vous effectuez une séquence de n insertions uniquement dans le tas. Le coût réel de l'exécution de ces opérations peut être de Θ (n log n) si chaque élément doit faire des bulles jusqu'en haut du tas. Cependant, le coût amorti de ces opérations, avec ce schéma comptable, serait de O (n), puisque nous avons effectué n opérations et prétendu que chacune coûtait O (1) temps. Par conséquent, ce schéma comptable amorti ne fonctionne pas, car il nous permettra de sous-estimer le travail que nous faisons.
D'un autre côté, regardons l'option 2, où nous affectons O (log n) comme notre coût d'insertion amorti et O (1) comme notre coût de retrait amorti. Maintenant, peut-on trouver une séquence de n opérations où le coût réel de ces opérations dépasse les coûts amortis? Dans ce cas, la réponse est non. Voici une façon de voir cela. Nous avons fixé le coût amorti d'une insertion à O (log n), ce qui correspond à son coût réel, et donc la seule façon dont nous pourrions finir par sous-estimer le total est avec notre coût amorti d'une suppression (O (1) ), ce qui est inférieur au coût réel d'une suppression. Cependant, ce n'est pas un problème ici. Pour que nous puissions effectuer une opération de suppression, nous devons avoir préalablement inséré l'élément que nous supprimons. Le coût réel combiné de l'insertion et de la suppression est O (log n) + O (log n) = O (log n), et le coût amorti combiné de l'insertion et de la suppression est O (log n) + O (1 ) = O (log n). Donc, en ce sens, prétendre que les suppressions sont plus rapides ne change pas notre coût global.
Une bonne manière intuitive de voir pourquoi la deuxième approche fonctionne mais pas la première consiste à réfléchir à ce qu'est l'analyse amortie. L'intuition derrière l'amortissement est de facturer un peu plus les opérations antérieures afin que les opérations futures semblent prendre moins de temps. Dans le cas du second schéma comptable, c'est exactement ce que nous faisons: nous reportons le coût de la suppression d'un élément du tas binaire sur le coût d'insertion de cet élément dans le tas en premier lieu. De cette façon, puisque nous ne faisons que reculer le travail, la somme des coûts amortis ne peut pas être inférieure à la somme des coûts réels. D'un autre côté, dans le premier cas, nous faisons avancer le travail dans le temps en faisant payer les suppressions pour les insertions. Mais c'est un problème, car si nous faisons un tas d'insertions et ensuite ne faisons jamais les suppressions correspondantes, nous aurons déplacé le travail vers des opérations qui n'existent pas.
Étant donné que le tas est initialement vide, vous ne pouvez pas avoir plus de suppressions que d'insertions.
Un coût amorti de O (1) par suppression et O (log N) par insertion est exactement le même qu'un coût amorti de O (log N) pour les insertions et les suppressions, car vous pouvez simplement compter le coût de suppression lorsque vous effectuez le insert correspondant.
Cela ne fonctionne pas dans l'autre sens. Étant donné que vous pouvez avoir plus d'insertions que de suppressions, il se peut qu'il n'y ait pas assez de suppressions pour payer le coût de chaque insertion.