Сложность list.index (x) в Python - PullRequest
23 голосов
/ 06 мая 2011

Я имею в виду это: http://docs.python.org/tutorial/datastructures.html

Каким будет время работы функции list.index(x) в терминах больших цифр O?

Ответы [ 6 ]

32 голосов
/ 06 мая 2011

Это O (n), также проверьте: http://wiki.python.org/moin/TimeComplexity

На этой странице описывается сложность времени (также называемая "Big O" или "Big Oh") различных операций в текущем CPython. Другие реализации Python (или более старые или все еще находящиеся в стадии разработки версии CPython) могут иметь немного другие характеристики производительности. Тем не менее, как правило, можно с уверенностью предположить, что они не медленнее, чем с коэффициентом O (log n) ...

8 голосов
/ 06 мая 2011

Согласно указанной документации:

list.index(x)

Вернуть индекс в списке первого элемента, значение которого равно x.Это ошибка, если такого элемента нет.

Что подразумевает поиск.Вы фактически делаете x in s, но вместо возврата True или False вы возвращаете индекс x.Таким образом, я бы пошел с перечисленной временной сложностью из O (n).

1 голос
/ 07 мая 2011

Любая реализация списка будет иметь сложность O (n) для линейного поиска (например, list.index). Хотя, может быть, есть какие-то дурацкие реализации, которые делают хуже ...

Вы можете улучшить сложность поиска, используя различные структуры данных, такие как упорядоченные списки или наборы. Обычно они реализуются с помощью бинарных деревьев. Однако эти структуры данных накладывают ограничения на элементы, которые они содержат. В случае двоичного дерева элементы должны быть упорядочены, но стоимость поиска снижается до O (log n).

Как упоминалось ранее, посмотрите здесь стоимость времени выполнения стандартных структур данных Python: http://wiki.python.org/moin/TimeComplexity

0 голосов
/ 22 мая 2019

Используйте следующий код для проверки времени.Его сложность 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)")
0 голосов
/ 15 октября 2018

Представленная выше документация не охватывала list.index ()

, насколько я понимаю, list.index - это операция O (1).Вот ссылка, если вы хотите узнать больше.https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

0 голосов
/ 08 июня 2016

Попробуйте этот код, он поможет вам получить время выполнения, необходимое оператору lis.index.

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