Le temps de la complexité pour java ArrayList

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)?

InformationsquelleAutor Hidayat | 2010-02-02
  1. 109

    Un ArrayList en Java est un List qui est soutenu par une array.

    La get(index) méthode est une constante de temps, O(1), 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)

    • Il est temps constant parce que tableau[n]----signifie que le système va juste faire un calcul mathématique= offsetvalue + (taille de la Variable)*n. donc toute cette histoire de calcul qui va se passer dans le processeur sans avoir à accéder aux emplacements de mémoire, encore et encore.c'est pourquoi il est O(1)
    InformationsquelleAutor jjnguy
  2. 20

    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 dans amorti de la constante de temps,
    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.

    InformationsquelleAutor tangens
  3. 12

    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.

    • C'est un peu hors-sujet, mais j'ai de la haine pour quelqu'un de se confondre et pas vraiment d'avis l'accent sur get les opérations.
    • Dans le JDK code je suis à la recherche d' (1.6.0_17), la nouvelle capacité est en fait calculé comme (oldCapacity * 3)/2 + 1.
    • Ergoter sur la première phrase, qui semble impliquer que les opérations d'écriture s'exécuter en O(n) fois. Ce n'est pas ce que le doc a dit, il dit que ajout de n éléments nécessite O(n). Pour des éléments individuels, l'insertion est toujours en O(1). La ré-allocation, copier, etc. il suffit de le rendre un peu plus "grand" O(1).
    • Vous pouvez éviter l'expansion des étapes si vous dites le constructeur comment grand il devrait être depuis le début. (si vous connaissez)
    • Salut Carl Smotricz, Comment est réaffectation est "un peu \"plus\" O(1)" ? Par exemple, si vous avez la taille du tableau 16. Si vous essayez d'ajouter le 17e élément, puis tous les 16 éléments précédents doit être exemplaires sur le nouveau tableau qui est O(n) qui est la grosse différence par rapport à O(1) ...
    • ouais, c'est pourquoi il dit amortis à temps constant. La plupart des insertions O(1), mais chaque maintenant et puis ils seront en O(n). Pris dans leur ensemble, les insertions se comporter comme O(1).
    • Pourquoi le redimensionnement de ne pas compter dans le cadre de l'ajouter, si? Ma pensée est que depuis dans l'ajout de n éléments que vous aurez besoin pour faire croître le tableau quelque part autour de log2(n) fois (donner ou prendre quelques-uns, mais c'est constant WRT n), et la croissance de la matrice prend O(n) à chaque fois qu'il doit être fait, la durée moyenne de la complexité serait en fait O(n log n). Est-il une raison pour que la croissance évènements n'ont pas besoin d'être pris en compte?
    • Le temps de redimensionner est prise en compte, mais votre rapprochement est pessimiste. Lors de l'ajout de n éléments, vous avez effectué n réelles insertions, et log(n) tableau des affectations/copier. Mais ces répartition ne coûte pas n, mais respectivement 2, 4, 8, 16, 32, etc. Si l'insertion d'un élément de coût, et de l'allocation de+copymemory coût Bk, où k est la taille de l'allocation d'un tableau, le coût final est Unn + B + 2*B + 4*B + 8*B + ... + 2n*B (dans le pire des cas) <= (A + 4B)*n, qui est linéaire.

    InformationsquelleAutor Kristopher Ives
  4. 4

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

    InformationsquelleAutor Carl Smotricz
  5. 0

    Juste une Remarque.

    La get(index) méthode est une constante de temps, O(1)

    Mais c'est le cas, si nous savons l'index. Si nous essayons d'obtenir l'index de l'aide de indexOf(something), d'un coût de O(n)

    • "Se indexOf pour certains élément est O(n), de toute façon.
    InformationsquelleAutor prime