Big O analyse du coût d'exécution de récupération de place

Question

Lorsque vous raisonnez sur le coût d'exécution dans une langue collectée, quel est le coût d'une instruction comme myList = null; en termes de 'n' (le nombre d'éléments dans la liste)? Par souci d'argument, considérez la liste comme étant une liste de types de références à liaison unique sans finalisation requise. Plus généralement, je cherche des informations sur la façon dont le coût d'exécution peut être analysé dans un langage avec GC.

Answer 1

Ma propre pensée est que le coût est susceptible d'être O (1) ou O (n) selon l'implémentation du collecteur. Dans un collecteur de marques et de balayages, les objets inaccessibles ne seront tout simplement pas atteints, donc je pourrais imaginer qu'il n'y a pas de coût associé à les effacer. En fait, dans un simple collecteur de comptage de références, j'imagine facilement qu'il en coûte O (n) pour faire le nettoyage ...

Ce n'est pas évident pour moi comment raisonner à ce sujet lors de la conception des algorithmes ..

Answer 2

Je suppose que vous pouvez supposer the amortized costs de cette déclaration à O (1). En pratique, c'est ce que je fais, et je n'ai jamais trouvé de situation qui m'a fait soupçonner cette hypothèse d'être incorrecte.