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

В Python, доступ к элементу списка по индексу (например, my_list[42]) имеет константную временную сложность O(1). Это связано с тем, что списки в Python реализованы как массивы динамического размера, где доступ к любому элементу происходит за фиксированное время, независимо от его позиции в списке.

Причина: Python-списки хранят ссылки на элементы в непрерывном блоке памяти. Доступ по индексу — это просто вычисление смещения от начала блока и получение значения по этому адресу, что занимает постоянное время.

Пример:

my_list = [1, 2, 3, 4, 5]
# Время доступа не зависит от индекса и размера списка
print(my_list[0])  # O(1)
print(my_list[len(my_list) - 1])  # O(1)

Нюансы:

• Отрицательные индексы (например, my_list[-1]) также обеспечивают доступ за O(1), так как они преобразуются в положительные индексы (len(my_list) - 1).
• Операции среза (my_list[1:3]) имеют сложность O(k), где k — размер создаваемого среза, поскольку требуется копирование k элементов в новый список.