Сложность list.index (x) в Python

18

Я имею в виду: Ссылка

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

задан user734027 06.05.2011 в 17:34
источник

4 ответа

24

Это O (n), также проверьте: Ссылка

  

Эта страница документирует сложность времени (иначе «Big O» или «Big Oh») различных операций в текущем CPython. Другие реализации Python (или более старые или все еще разрабатываемые версии CPython) могут иметь несколько иные характеристики производительности. Однако, как правило, безопасно предположить, что они не медленнее более чем на 0 (log n) ...

    
ответ дан zeekay 06.05.2011 в 17:40
  • просто добавить, поскольку индексный алгоритм может применяться в списке или других структурах данных, он реализуется как линейный поиск, следовательно, O (n). –  darth_coder 08.05.2015 в 12:11
7

В соответствии с указанной документацией:

list.index(x)
     

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

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

    
ответ дан user257111 06.05.2011 в 17:41
  • Почему он не возвращает -1 вместо ошибки. –  darth_coder 08.05.2015 в 12:12
  • @darth_coder вы найдете функцию для этого –  ultramarine 20.07.2017 в 20:49
1

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

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

Как уже упоминалось ранее, посмотрите на затраты времени на запуск стандартных структур данных Python: Ссылка

    
ответ дан Alex Smith 07.05.2011 в 06:25
-2

Попробуйте этот код, это поможет вам получить время выполнения, сделанное оператором 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)
    
ответ дан Chin Danzal 08.06.2016 в 05:31