Je me demande quelle est la complexité temporelle de la méthode pop des objets de liste en Python (en particulier dans CPython). Est-ce que la valeur de N pour list.pop (N) affecte également la complexité?Quelle est la complexité temporelle de l'éclatement des éléments de la liste en Python?
Pop()Pop() pour le dernier élément doit être O (1) car il suffit de renvoyer l'élément référencé par le dernier élément du tableau et de mettre à jour l'index du dernier élément. Je m'attendrais pop() pour qu'un élément arbitraire soit O (N) et exige en moyenne N/2 opérations puisque vous auriez besoin de déplacer tous les éléments au-delà de l'élément que vous supprimez une position dans le tableau de pointeurs.
Oui, il est O (1) pour faire apparaître le dernier élément d'une liste de python, et O (N) pour faire apparaître un élément arbitraire (puisque tout le reste de la liste doit être décalée).
Voici un article sur la façon dont les listes Python sont stockées et manipulées: http://effbot.org/zone/python-list.htm
Donc, juste pour le rendre clair, list.pop (0) est O (n) et list.pop() est O (1). –
Et pour obtenir les deux opérations dans O (1), utilisez collections.deque voir [ici] (https://wiki.python.org/moin/TimeComplexity) – galath
La réponse courte est de regarder ici: https://wiki.python.org/moin/TimeComplexity
Sans argument pour faire apparaître son O (1)
Avec une argument à pop:
complexité temporelle moyenne:
Chaque fois que vous mettez dans un valeur la complexité temporelle de cette opération est O (n - k).
Par exemple, si vous avez une liste de 9 articles que la suppression de la fin de la liste est de 9 opérations et le retrait depuis le début de la liste est de 1 opérations (suppression de l'indice 0e et se déplaçant tous les autres éléments à leur index actuel - 1)
Puisque n - k pour l'élément central d'une liste est k opérations, la moyenne peut être raccourcie à O (k). Une autre façon de penser à cela est d'imaginer que chaque index a été supprimé une fois de votre liste de 9 éléments. Ce serait un total de 45 opérations. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
45 est égal à O (nk) et puisque l'opération pop s'est produite O (n) fois que vous divisez nk par n pour obtenir O (k)
amorti pire moment complexité des cas
Imaginez que vous avez une liste de 9 articles à nouveau.Imaginez que vous supprimez tous les éléments de la liste et que le pire des cas se produit et que vous supprimez le premier élément de la liste à chaque fois.
Puisque la liste se rétrécit de 1 chaque fois le nombre d'opérations totales diminue chaque fois à partir de 9 à 1.
9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 45 est égal à O (nk). Puisque vous avez effectué 9 opérations et que 9 est O (n) pour calculer le pire scénario, vous faites O (nk)/O (n) qui est égal à O (k)
En indiquant c'est O (n) pour la moyenne et la complexité du temps le plus défavorable amorti est également correcte. Notez que O (k) est d'environ O (1/2n) et laissant tomber la constante est égale à O (n)
pire moment complexité des cas
Je suis d'accord avec la réponse donnée, mais l'explication est AMHA mal. Vous pouvez supprimer n'importe quel objet d'une liste à O (1) (faire essentiellement pointer le point prev à next, et l'enlever) Le problème est que pour TROUVER l'objet à cette position, vous devez parcourir la liste jusqu'à ce que point (prend le temps O (N), aucune moyenne nécessaire.) Enfin une note de cas spéciale :, pop (0) prendra O (1), pas O (0). – ntg
@ntg la liste est un tableau de pointeurs. pour supprimer un pointeur du tableau au milieu, tous les pointeurs qui le suivent doivent être déplacés dans le tableau en prenant un temps proportionnel à la taille de la liste (que nous notons N), donc O (N) . Clarifier le N dans la notation Big-O n'est PAS l'indice de l'élément renvoyé, mais une fonction limitant le temps de fonctionnement de l'algorithme avec O (1) étant un temps constant - c'est-à-dire qu'il ne dépend pas de la taille de la liste. O (N) signifie que la fonction de délimitation est une constante de la taille de la liste, f (n) = c * n + b. – tvanfosson
Je suis corrigé :) En effet, l'implémentation de la liste est un tableau de pointeurs. Donc, votre réponse est correcte. Par pop (N) dans votre réponse vous voulez dire pop (k), N où k est la position de l'élément à enlever, et la taille de ce tableau est N. Puis k peut aller de 0 à N-1, donc par N moyenne/2 opérations pour déplacer les éléments k + 1, ...., N-1 une position vers l'arrière. – ntg