Какое «time complexity» имеет операция list[element]?

Question

[harliy]

К примеру, есть список list = [one, two, three]. Если я напишу element = list[2], то программа моментально сделает эту операцию O(1) или прочитает весь список O(n)?

Answer 1

[Roman K]

https://wiki.python.org/moin/TimeComplexity

list в питоне — это по сути массив (точнее — вектор) указателей на *PyObject. Адрес начала известен. Размер элемента известен. Поэтому элементарная арифметика указателей адрес_начала + (sizeof(PyObject) * X) — за O(1)

Answer 2

[Максим Припадчев]

Программа выполнится с 0(1), никакого чтения всего листа не произойдет. Потому что все вы делаете это получаете элемент по индексу. Например если изменить немножко вопрос скажем у нас есть список и словарь.
'B' in ['A', 'B','C'] Вот это операция будет O(n)
В то время как
'B' in {'A':1,'B':2,'C':3}
останется O(1).
Ну и напоследок если список отсортирован и python знает что он отсортирован то проверка на наличие элемнта в списке будет тоже O(1).

ОТРЕДАКТИРОВАНО

Ну и напоследок если список отсортирован и python знает что он отсортирован то проверка на наличие элемнта в списке будет тоже O(1).

Это утверждение абсолютно неверно. На мою ошибку указал Roman K В комментарии к моему ответу.

Comments

[Roman K]

Нет никакого «python знает что он отсортирован» и никакого O(1). Зачем ты обманываешь людей?

Более того, даже если ты сам знаешь, что список отсортирован, то можешь найти элемент за O(logN) и не быстрее.

[Максим Припадчев]

Roman K, Ну во первых не хами, а во вторых я имел ввиду если создать список [1,2,3] то для python он не является отсортированным пока его не отсортировать.

[Максим Припадчев]

Roman K, Посмотрел, ссылки действительно O(logN), значит даже на отсортированном списке размер списка имеет значение. То есть при экспонентном росте размера, время исполнения будет расти линейно. Что же я действительно ошибся. Но это абсолютно не повод хамить.

[Roman K]

Максим Припадчев, хамить в чем? Ты обманываешь людей? Обманываешь. Выдаёшь мнение за факты? Выдаёшь. Я не хамлю, я говорю факты.

[Максим Припадчев]

. Roman K, Ответ с ошибкой не является обманом. А с тобой я не считаю нужным вести беседу