Complexité temporelle pour Java ArrayList
j'ai trouvé d'autres entrées pour cette question qui traitent de méthodes spécifiques, mais rien de complet. J'aimerais vérifier ma propre compréhension des méthodes les plus souvent utilisées de cette structure de données:
O(1) Constante De Temps:
isEmpty()
add(x)
add(x, i)
set(x, i)
size()
get(i)
remove(i)
O(N) - Le Temps Linéaire:
indexof(x)
clear()
remove(x)
remove(i)
Est-ce correct? Merci pour votre aide.
1 réponses
La meilleure ressource est directement à partir de l' API officielle:
les opérations de taille, isEmpty, get, set, iterator, et listIterator s'exécutent en temps constant. L'opération d'ajout s'exécute en temps constant amorti, qui est, l'ajout de n éléments nécessite O(n) fois. Toutes les autres opérations fonctionnent en temps linéaire (en gros). Le facteur constant est faible comparé à celui de la mise en œuvre de la liste de liens.