Complexité temporelle en Java

Pour la méthode add () de la liste de tableaux API Java états:

L'ajouter exploitation s'exécute en temps constant amorti, qui est, l'ajout de n éléments nécessite O(n) fois.

Je me demande si c'est la complexité en même temps, linéaire, lors de l'utilisation de la méthode add de un LinkedList.

InformationsquelleAutor FranXh | 2012-02-12
  1. 9

    Cela dépend où vous êtes en train d'ajouter. E. g. si dans une liste de tableaux que vous ajoutez à l'avant de la liste, la mise en œuvre du changement de tous les éléments à chaque fois, donc, l'ajout de n éléments s'exécutent dans quadratique du temps.

    Similaire pour la liste chaînée, la mise en œuvre dans le JDK conserve un pointeur vers la tête et la queue. Si vous continuez à ajouter du texte à la queue, ou en ajoutant le devant de la tête, l'opération ne s'exécute en temps linéaire de n éléments. Si vous ajoutez à un endroit différent, la mise en œuvre, à la recherche de la liste pour le bon endroit, ce qui vous donnera peut-être le pire moment de l'exécution. Encore une fois, cela dépend de la position d'insertion; vous aurez le pire moment de la complexité si vous êtes à l'insertion dans le milieu de la liste, comme le nombre maximal d'éléments doivent être parcourus pour trouver le point d'insertion.

    La complexité réelle dépend de la position d'insertion est constante (par exemple, toujours à la 10e position), ou une fonction du nombre d'éléments dans la liste (ou de certains d'arbitraire recherche sur elle). Le premier vous donnera O(n) avec un peu pire facteur constant, le dernier O(n^2).

    • Ok, c'est logique. J'ajoute à l'avant de l'listes pour la liste de tableaux sera quadratique alors, et pour la liste liée linéaire
    • Vrai, mais en ajoutant à l'avant est mieux fait avec ArrayDeque qui excel pour cette tâche. Il y en a presque toujours sont des structures mieux que LinkedList 🙂
    • L'ajout d'un élément à la tête d'une liste de tableaux ne serait pas en O(1), mais plutôt de O(n) comme Martins a dit:.
    InformationsquelleAutor Martin Probst
  2. 4

    Dans la plupart des cas, ArrayList surpasse LinkedList sur le add() de méthode, c'est tout simplement l'enregistrement d'un pointeur sur un tableau et l'incrémentation du compteur.

    Si la woking tableau n'est pas assez grande, bien que, ArrayList pousse travail tableau, l'allocation d'un nouveau et de copier le contenu. C'est plus lent que l'ajout d'un nouvel élément à LinkedList—mais si vous avez constamment ajouter des éléments, qui se produit seulement O(log(N)) fois.

    Lorsque nous parlons de "amorti" la complexité, nous prendre un temps moyen calculé pour certains, la tâche de référence.

    Donc, pour répondre à votre question, ce n'est pas la même complexité: il est beaucoup plus rapide (bien que toujours O(1)) dans la plupart des cas, et beaucoup plus lent (O(N)) parfois. Quoi de mieux pour vous est de mieux vérifié avec un profiler.

    InformationsquelleAutor alf
  3. 3

    Si vous voulez dire la add(E) méthode (pas le add(int, E) méthode), la réponse est oui, le temps de la complexité de l'ajout d'un élément unique dans une LinkedList est constante (ajout de n éléments nécessite O(n) le temps)

    Comme Martin Probst indique, avec des positions différentes, vous obtenez différentes complexités, mais le add(E) opération de toujours ajouter l'élément à la queue, résultant en une constante (amorti) temps de fonctionnement

    • add(E) opération de toujours ajouter l'élément à la queue, résultant en une constante de temps de fonctionnement — pas exactement vrai, il peut bien être O(N) pour ArrayList.
    • C'est vrai, lorsque le ArrayList atteint sa limite et doit être régénéré. J'ai ajouté une aclaration qu'il fonctionne dans constant (amorti) temps
    InformationsquelleAutor rodrigo.garcia