Le temps de la complexité pour java ArrayList

Question

Est - ArrayList d'un tableau ou d'une liste en java? quel est le temps de la complexité de l'opération d'acquisition, est-il O(n) ou O(1)?

Answer 1

Un ArrayList en Java est un List , soutenu par un array.

L' get(index) méthode est un temps constant, O(1), l'opération.

Le code tout droit sorti de la bibliothèque Java pour ArrayList.get(index):

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

Fondamentalement, elle retourne une valeur tout droit sorti de la sauvegarde de la matrice. (RangeCheck(index)) est également une constante de temps)

Answer 2

C'est la mise en œuvre se fait avec un tableau et l'opération get est O(1).

javadoc dit:

La taille, isEmpty, get, set, itérateur, et listIterator des opérations en constante temps. L'opération d'ajout s'exécute en temps constant amorti, c'est, en ajoutant n éléments nécessite O(n) fois. Toutes les autres opérations de exécuter en temps linéaire (grosso modo). Le facteur constant est faible par rapport pour la LinkedList mise en œuvre.

Answer 3

Comme tout le monde l'a déjà souligné, les opérations de lecture sont à temps constant O(1) mais les opérations d'écriture ont le potentiel de manquer d'espace dans la sauvegarde de tableau, la ré-allocation, et copie - donc, qui s'exécute en O(n) le temps, comme le doc a dit:

La taille, isEmpty, get, set, itérateur, et listIterator opérations sont exécutées dans la constante de temps. L'opération d'ajout fonctionne en temps constant amorti, qui est, l'ajout de n éléments nécessite O(n) fois. Toutes les autres opérations sont exécutées dans le temps linéaire (grosso modo). L' facteur constant est faible par rapport à que pour la LinkedList la mise en œuvre.

Dans la pratique, tout est O(1), après quelques ajoute, depuis le support de tableau est doublé à chaque fois c'est la capacité est épuisé. Donc, si le tableau commence à 16, est plein, il est réaffecté à 32, 64, 128, etc. alors qu'il évolue bien, mais GC peut toucher jusqu'au cours d'une grande realloc.

Answer 4

Pour être pédant, c'est un List soutenu par un tableau. Et oui, la complexité du temps pour get() O(1).