La complexité de la liste.index(x) en Python

Je fais référence à ceci: http://docs.python.org/tutorial/datastructures.html

Ce serait le temps d'exécution de list.index(x) fonction en termes de notation grand O?

  • Vous pouvez trouver le code source pour l'opération d'index ici. Il est O(n).
InformationsquelleAutor user734027 | 2011-05-06
  1. 32

    Il est O(n), consultez également: http://wiki.python.org/moin/TimeComplexity

    Cette page les documents de l'époque-de la complexité (alias "Big O" ou "Big O"), de diverses opérations de courant Disponible. D'autres implémentations de Python (ou plus, ou encore sous des versions de développement de Disponible) sont légèrement différentes caractéristiques de performance. Toutefois, il est généralement prudent de supposer qu'ils ne sont pas plus lent par plus d'un facteur O(log n)...

    • juste pour ajouter depuis que l'indice de l'algorithme peut être appliqué sur list ou d'autres structures de données, c'est mettre en œuvre que la recherche linéaire donc O(n).
    InformationsquelleAutor zeekay
  2. 8

    Selon la dite documentation:

    list.index(x)

    Retour à l'index dans la liste du premier élément dont la valeur est x.
    C'est une erreur si il n'y a aucune de ces questions.

    Qui implique la recherche. Vous êtes effectivement faire x in s mais plutôt que de retourner True ou False vous êtes de retour à l'index de x. En tant que tel, j'irais avec le temps indiqué complexité de O(n).

    • Pourquoi ne pas les retours -1 au lieu d'une erreur.
    • vous avez find fonction pour que
    InformationsquelleAutor
  3. 1

    Une liste de mise en œuvre va avoir un O(n) la complexité pour un linéaire de recherche (p. ex., liste.l'indice). Bien que peut-être il y a quelques farfelus les implémentations qui n'est pas la pire...

    Vous pouvez améliorer la recherche de la complexité à l'aide de différentes structures de données, telles que des listes ordonnées ou des ensembles. Ces sont généralement mises en œuvre avec des arbres binaires. Cependant, ces structures de données de mettre des contraintes sur les éléments qu'ils contiennent. Dans le cas d'un arbre binaire, les éléments doivent être disponible sur commande, mais la recherche de coût descend à O(log n).

    Comme mentionné précédemment, regardez ici pour exécuter des coûts de temps de standard de Python structures de données:
    http://wiki.python.org/moin/TimeComplexity

    InformationsquelleAutor Alex Smith
  4. 0

    Utiliser le code suivant pour vérifier le calendrier. Sa complexité est O(n).

    import time


class TimeChecker:

    def __init__(self, name):
        self.name = name

    def __enter__(self):
        self.start = self.get_time_in_sec()
        return self

    def __exit__(self, exc_type, exc_val, exc_tb):
        now = self.get_time_in_sec()
        time_taken = now - self.start  # in seconds
        print("Time Taken by " + self.name + ": " + str(time_taken))

    def get_time_in_sec(self):
        return int(round(time.time() * 1000))


def test_list_index_func(range_num):
    lis = [1,2,3,4,5]
    with TimeChecker('Process 1') as tim:
        for i in range(range_num):
            lis.index(4)

test_list_index_func(1000)
test_list_index_func(10000)
test_list_index_func(100000)
test_list_index_func(1000000)

print("Time: O(n)")
    InformationsquelleAutor Geetesh Gupta
  5. -1

    La documentation fournie ci-dessus ne couvrent pas la liste.index()

    à partir de ma compréhension, liste.l'indice est O(1) de l'opération.
    Voici un lien si vous voulez en savoir plus. https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

    • Vous êtes dans l'erreur. L ' "Indice" que votre lien est de parler de la même chose que d'Obtenir de l'Élément dans le python.org wiki. Vous pouvez le voir dans la disponible le code source que la méthode de l'indice est en train de faire un O(n) la recherche de la liste.
    InformationsquelleAutor A story-teller
  6. -3

    Essayer ce code, il vous aidera à obtenir votre temps d'exécution prises par lis.l'indice de l'opérateur.

    import timeit
lis=[11,22,33,44,55,66,77] 
for i in lis: 
    t = timeit.Timer("lis.index(11)", "from main import lis") 
    TimeTaken= t.timeit(number=100000) 
    print (TimeTaken)
    InformationsquelleAutor Chin Danzal