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

Ответ 1

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

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

Ответ 2

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

list.index(x)

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

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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