Python - Analyse amortie
L'analyse amortie consiste à estimer le temps d'exécution de la séquence d'opérations dans un programme sans prendre en considération l'étendue de la distribution des données dans les valeurs d'entrée. Un exemple simple est que la recherche d'une valeur dans une liste triée est plus rapide que dans une liste non triée. Si la liste est déjà triée, peu importe la répartition des données. Mais bien sûr, la longueur de la liste a un impact car elle décide du nombre d'étapes que l'algorithme doit franchir pour obtenir le résultat final.
Nous voyons donc que si le coût initial d'une seule étape d'obtention d'une liste triée est élevé, alors le coût des étapes ultérieures de recherche d'un élément devient considérablement faible. Ainsi, l'analyse amortie nous aide à trouver une limite sur le temps d'exécution le plus défavorable pour une séquence d'opérations. Il existe trois approches de l'analyse amortie.
Accounting Method- Il s'agit d'attribuer un coût à chaque opération effectuée. Si l'opération réelle se termine plus rapidement que le temps imparti, un crédit positif est accumulé dans l'analyse. Dans le scénario inverse, ce sera un crédit négatif. Pour garder une trace de ces crédits accumulés, nous utilisons une structure de données en pile ou en arbre. Les opérations qui sont effectuées tôt (comme le tri de la liste) ont un coût amorti élevé, mais les opérations qui sont en retard dans la séquence ont un coût amorti inférieur à mesure que le crédit accumulé est utilisé. Le coût amorti est donc une limite supérieure du coût réel.
Potential Method- Dans cette méthode, le crédit enregistré est utilisé pour des opérations futures en tant que fonction mathématique de l'état de la structure de données. L'évaluation de la fonction mathématique et le coût amorti doivent être égaux. Ainsi, lorsque le coût réel est supérieur au coût amorti, le potentiel diminue et il est utilisé pour des opérations futures qui sont coûteuses.
Aggregate analysis - Dans cette méthode, nous estimons la limite supérieure du coût total de n étapes. Le coût amorti est une simple division du coût total et du nombre d'étapes (n).