Il y a une question similaire sur Hash (dictionnaires) et listes, il existe également une bonne œuvre d'informations ici: http://wiki.python.org/moin/timecomplexity
mais je n'ai rien trouvé sur les tuples. p>
L'heure d'accès pour P>
data_structure[i]
Qu'en est-il de tuple? Est-ce o (n) comme pour une liste liée ou o (1) comme pour un tableau? P> p>
4 Réponses :
Il devrait être Mais pour les listes Python, je m'attendrais à O (1) , car il n'est vraiment qu'une liste.
O (1) aussi! Vous voudrez peut-être y réfléchir à nouveau ...
Un tuple n'est pas une liste. C'est une séquence, mais c'est tout.
C'est O (1) pour la liste et le tuple. Ils sont tous deux moralement équivalents à un réseau indexé entier.
@Tkerwin Je veux dire que dans le contexte de cette question, à toutes fins utiles, vous êtes en sécurité de considérer les listes et les tuples en tant que réseaux indexés entier.
La curiosité est moralement équivalente souvent utilisée pour signifier cela au Royaume-Uni?
@ Marr75 Je l'utilise assez souvent ici au Royaume-Uni ;-) Faites une recherche sur "Equivalent moral" et ajoutez quelques termes de programmation, par ex. Goto, retour, exception et vous verrez que je ne suis pas seul.
Je l'obtiens avec "goto" car il y a des débats sur la "malvoi" de goto, alors peut-être que c'est sa racine? Semble plus applicable aux débats sur les caractéristiques du code graphique ou de la langue soustraire de la convivialité, mais je garderai à l'esprit que l'utilisation augmente. Merci.
Que diriez-vous de vérifier si un élément existe dans un tuple? 3 po (1,2,3). Est-ce aussi O (1) ou O (n) comme une liste?
@Bigdreamz o (n)
Les listes et les tuples sont indexables de la même manière que les tableaux sont dans d'autres langues.
Une explication simplifiée est que l'espace est attribué aux références aux objets, ces références occupent une quantité d'espace uniforme et tout index est simplement multiplié par la taille de la référence pour obtenir un décalage dans la matrice. Cela donne constamment, O (1), accès aux listes et aux tuples.
Merci de clarification, mais ici, j'ai une question sur INSERT dans la liste: comme c'est comme une matrice, cela signifie que cela signifie que l'insertion n'est pas O (1)? Vous pouvez également donner un lien ici avec des informations sur la complexité temporelle des structures de données Python?
Votre question n'a pas mentionné des insertions et, en fait, vous semblez être claire sur les timings pour une liste. Vous avez déjà donné un lien avec ce que j'appellerais les informations les plus définitives sur la complexité temporelle des structures de données Python.
Obtenir un élément à partir d'une liste liée est O (n), mais les listes Python ont des implémentations basées sur des matrices afin que le coût soit O (1).
Les tuples sont également implémentés à l'aide de tableaux afin qu'il soit O (1) pour eux aussi.
pour la liste est O (n) en général faux. Sauf si vous parlez de listes liées, qui n'existent nulle part dans la bibliothèque standard de Python. Qu'est-ce que Python appelle "liste" est une graphique dynamique et donc a o (1) l'accès de l'article. (Au fait, la page que vous liez dit exactement cela.)La complexité de temps pour obtenir un article dans une liste est O (1), je suppose que c'est la même chose pour un tuple.