algorithm big - Temps amorti constant




3 Answers

Le temps amorti expliqué en termes simples:

Si vous faites une opération un million de fois, vous ne vous souciez pas vraiment du cas le plus défavorable ou du meilleur de cette opération - ce qui vous intéresse, c'est combien de temps vous prenez au total lorsque vous répétez l'opération un million de fois .

Donc, peu importe si l'opération est très lente de temps en temps, du moment que "de temps en temps" est assez rare pour que la lenteur soit diluée. Le temps essentiellement amorti signifie «temps moyen pris par opération, si vous effectuez de nombreuses opérations». Le temps amorti n'a pas besoin d'être constant. vous pouvez avoir le temps amorti linéaire et logarithmique ou n'importe quoi d'autre.

Prenons l'exemple d'un tableau dynamique de tapis, auquel vous ajoutez de nouveaux éléments à plusieurs reprises. Normalement ajouter un élément prend un temps constant (c'est-à-dire O(1) ). Mais chaque fois que le tableau est plein, vous allouez deux fois plus d'espace, copiez vos données dans la nouvelle région et libérez l'ancien espace. En supposant que les allocations et les libérations s'exécutent en temps constant, ce processus d'agrandissement prend l'heure O(n) où n est la taille actuelle du tableau.

Donc, chaque fois que vous agrandissez, vous prenez environ deux fois plus de temps que le dernier agrandissement. Mais vous avez aussi attendu deux fois plus longtemps avant de le faire! Le coût de chaque élargissement peut ainsi être "étalé" entre les insertions. Cela signifie qu'à long terme, le temps total nécessaire pour ajouter m éléments au tableau est O(m) , et donc le temps amorti (c'est-à-dire le temps par insertion) est O(1) .

notation cheat

Qu'entend-on par "temps amorti constant" lorsqu'on parle de la complexité temporelle d'un algorithme?




Pour développer une façon intuitive d'y penser, considérez l'insertion d'éléments dans un tableau dynamique (par exemple std::vector en C ++). Traceons un graphique, qui montre la dépendance du nombre d'opérations (Y) nécessaires pour insérer N éléments dans le tableau:

Les parties verticales du graphe noir correspondent à des réallocations de mémoire afin d'élargir un tableau. Ici, nous pouvons voir que cette dépendance peut être grossièrement représentée comme une ligne. Et cette équation de ligne est Y=C*N + b ( C est constante, b = 0 dans notre cas). Par conséquent, nous pouvons dire que nous devons dépenser des opérations C*N en moyenne pour ajouter N éléments au tableau, ou des opérations C*1 pour ajouter un élément (temps constant amorti).




Les explications ci-dessus s'appliquent à l'analyse agrégée, l'idée de prendre «une moyenne» sur plusieurs opérations. Je ne suis pas sûr de la façon dont ils s'appliquent à la méthode des banquiers ou aux méthodes des physiciens de l'analyse amortie.

À présent. Je ne suis pas exactement sûr de la bonne réponse. Mais cela aurait à voir avec la condition principale des deux méthodes physiciens + banquiers:

(Somme du coût d'exploitation amorti)> = (Somme du coût réel des opérations).

La principale difficulté à laquelle je fais face est que, étant donné que les coûts d'exploitation amortissables asymptotiques diffèrent du coût asymptotique normal, je ne suis pas sûr de savoir comment évaluer l'importance des coûts amortis.

C'est quand quelqu'un me donne un coût amorti, je sais que ce n'est pas la même chose que le coût normal-asymptotique Quelles conclusions puis-je tirer du coût amorti alors?

Étant donné que certaines opérations sont surfacturées alors que d'autres opérations sont sous-facturées, une hypothèse pourrait être que le coût amorti des opérations individuelles n'aurait aucun sens.

Par exemple: Pour un tas de fibonacci, le coût amorti de seulement Decreasing-Key à O (1) n'a aucun sens puisque les coûts sont réduits par "le travail effectué par les opérations précédentes en augmentant le potentiel du tas".

OU

Nous pourrions avoir une autre hypothèse qui justifie les coûts amortis comme suit:

  1. Je sais que l'opération coûteuse sera précédée par des opérations à MULTIPLES COÛTS.

  2. Par souci d'analyse, je vais surcharger certaines opérations à bas prix, TELLES QUE LEUR COÛT ASYMPTOTIQUE NE CHANGE PAS.

  3. Avec ces opérations à faible coût augmenté, je peux prouver que l'opération coûteuse a un plus petit coût ASYMPTOTIQUE.

  4. J'ai donc amélioré / diminué le ASYMPTOTIC-BOUND du coût de n opérations.

Ainsi, l'analyse des coûts amortis + les limites des coûts amortis ne sont désormais applicables qu'aux opérations coûteuses. Les opérations bon marché ont le même coût asymptotique amorti que leur coût asymptotique normal.




Related

algorithm complexity-theory big-o