Какова сложность получения значения списка по индексу в Python и почему

Что проверяют

Знаете ли вы, что список это массив указателей, и можете ли объяснить оценку через устройство памяти.

Как отвечать

Сложность O(1), доступ за постоянное время.

Причина в реализации: list в CPython это не связный список, а динамический массив указателей на объекты (структура PyListObject хранит указатель на непрерывный блок PyObject**). Адрес элемента вычисляется арифметикой: база плюс индекс, умноженный на размер указателя. Одно вычисление и одно обращение к памяти, независимо от длины списка и от значения индекса.

Отрицательные индексы тоже O(1): интерпретатор прибавляет длину, которая хранится в самой структуре.

Полезно тут же назвать сложность соседних операций, потому что спрашивают обычно за этим:

• append амортизированно O(1): при нехватке места блок перевыделяется с запасом, поэтому редкое копирование за O(n) размазывается;
• insert(0, x) и pop(0) это O(n): сдвигается весь хвост. Если нужна очередь, берут collections.deque с O(1) с обоих концов;
• поиск x in list это O(n), а в set и dict в среднем O(1);
• срез это O(k) по длине среза, потому что создаётся новый список.

Оговорка про память: элементы лежат подряд, но это указатели, а сами объекты разбросаны по куче. Поэтому список чисел заметно тяжелее и хуже ложится на кэш, чем массив в C, и для численных задач берут array или numpy.

Где спотыкаются

Путают list со связным списком и называют O(n).

Считают insert(0, x) дешёвой операцией.

Ищут вхождение в списке внутри цикла и получают квадрат.

Не знают про амортизацию у append и называют её O(n).