Durée constante amortie

Question

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

Answer 1

J'ai créé ce simple script python script pour démontrer la complexité amortie de l'opération append dans une liste python. Nous continuons à ajouter des éléments à la liste et à chronométrer chaque opération. Au cours de ce processus, nous remarquons que certaines opérations d'ajout prennent beaucoup plus de temps. Ces pics sont dus à la nouvelle allocation de mémoire effectuée. Il est important de noter qu'au fur et à mesure que le nombre d'opérations d'ajout augmente, les pics deviennent plus importants mais s'espacent. L'augmentation de l'espacement est due au fait qu'une plus grande mémoire (généralement le double de la précédente) est réservée chaque fois que la mémoire initiale est débordée. J'espère que cela vous aidera, je peux encore l'améliorer en fonction de vos suggestions.

import matplotlib.pyplot as plt
import time

a = []
N = 1000000

totalTimeList = [0]*N
timeForThisIterationList = [0]*N
for i in range(1, N):
    startTime = time.time()
    a.append([0]*500) # every iteartion, we append a value(which is a list so that it takes more time)
    timeForThisIterationList[i] = time.time() - startTime
    totalTimeList[i] = totalTimeList[i-1] + timeForThisIterationList[i]
max_1 = max(totalTimeList)
max_2 = max(timeForThisIterationList)

plt.plot(totalTimeList, label='cumulative time')
plt.plot(timeForThisIterationList, label='time taken per append')
plt.legend()
plt.title('List-append time per operation showing amortised linear complexity')
plt.show()

On obtient le graphique suivant

Answer 2

La performance d'une fonction peut être calculée en divisant le "nombre total d'appels à la fonction" par le "temps total nécessaire pour tous ces appels". Même les fonctions qui prennent de plus en plus de temps à chaque appel peuvent encore être moyennées de cette manière.

Ainsi, l'essence d'une fonction qui fonctionne à Constant Amortized Time est que ce "temps moyen" atteigne un plafond qui ne soit pas dépassé au fur et à mesure que le nombre d'appels augmente. Les performances d'un appel particulier peuvent varier, mais à long terme, ce temps moyen ne continuera pas à augmenter.

C'est le mérite essentiel d'un produit qui fonctionne à Constant Amortized Time .

Answer 3

Les explications ci-dessus s'appliquent à l'analyse agrégée, c'est-à-dire à l'idée de prendre une "moyenne" sur plusieurs opérations. Je ne suis pas sûr de savoir comment elles s'appliquent à la méthode des banquiers ou aux méthodes d'analyse amortie des physiciens.

Maintenant. Je ne suis pas exactement sûr de la bonne réponse. Mais ça aurait à voir avec la condition de principe des deux physiciens + les méthodes de Banker :

(Somme des coûts d'exploitation amortis) >= (Somme des coûts d'exploitation réels).

La principale difficulté à laquelle je suis confronté est que, étant donné que les coûts d'exploitation asymptotiques amortis diffèrent des coûts asymptotiques normaux, je ne sais pas comment évaluer l'importance des coûts amortis.

En d'autres termes, lorsque quelqu'un me donne un coût amorti, je sais qu'il n'est pas identique au coût normal-asymptotique. Quelles conclusions dois-je tirer du coût amorti ?

Puisque nous sommes dans le cas où certaines opérations sont surtaxées alors que d'autres opérations sont soustaxées, une hypothèse pourrait être que le fait de citer les coûts amortis des opérations individuelles n'aurait aucun sens.

Par exemple : Pour un tas de fibonacci, citer le coût amorti d'une simple clé décroissante comme étant O(1) n'a aucun sens puisque les coûts sont réduits par "le travail effectué par les opérations précédentes pour augmenter le potentiel du tas".

OU

Nous pourrions avoir une autre hypothèse qui raisonne sur les coûts amortis de la manière suivante :

1. Je sais que l'opération coûteuse va être précédée de MULTIPLES opérations à faible coût.

2. Pour les besoins de l'analyse, je vais surtaxer certaines opérations à faible coût, de telle sorte que leur coût asymptotique ne change pas.

3. Grâce à l'augmentation des opérations à faible coût, je peux prouver qu'une opération coûteuse a un coût asymptotique plus faible.

4. J'ai donc amélioré/diminué la borne ASYMPTOTIQUE du coût des n opérations.

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

Answer 4

Durée d'utilisation amortie : Il s'agit du calcul de la complexité algorithmique en termes de temps ou de mémoire utilisée. par opération . Il est utilisé lorsque la plupart des opérations sont rapides mais que, dans certains cas, le fonctionnement de l'algorithme est lent. La séquence d'opérations est donc étudiée pour en savoir plus sur le temps amorti.