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

Алгоритмическая сложность чтения в списке Python

Алгоритмическая сложность чтения элемента из списка Python — O(1) (константная сложность). Это одна из главных особенностей списков в Python, обеспечивающая быстрый доступ к элементам независимо от их позиции.

Почему O(1)?

Потому что Python списки (list) реализованы как динамические массивы (resizable arrays). Это означает, что элементы хранятся в смежных ячейках памяти с прямыми адресами.

# Внутренняя структура списка
my_list = [10, 20, 30, 40, 50]

# Память выглядит так:
# Адрес: 1000  1008  1016  1024  1032
# Значение: 10   20   30   40   50
# (при предположении 8 байт на число)

# Доступ к элементу по индексу:
print(my_list[0])  # O(1) - идёт напрямую по адресу
print(my_list[4])  # O(1) - также напрямую
print(my_list[100])  # O(1) - но вызовет IndexError

Процессор может напрямую вычислить адрес элемента по индексу:

Адрес элемента = base_address + (index * sizeof(element))

Это вычисление делается за одну операцию, откуда и O(1).

Подтверждение на практике

import time

def measure_access_time(size, positions):
    my_list = list(range(size))
    
    for pos in positions:
        start = time.perf_counter()
        for _ in range(1000000):
            _ = my_list[pos]
        elapsed = time.perf_counter() - start
        print(f"Позиция {pos:>7}: {elapsed:.4f}s")

print("Список из 1,000,000 элементов:")
measure_access_time(1000000, [0, 500000, 999999])
# Времена будут примерно одинаковыми!

# Примерный результат:
# Позиция       0: 0.1234s
# Позиция  500000: 0.1235s
# Позиция  999999: 0.1236s

Сложность других операций со списками

# Чтение по индексу
my_list[5]  # O(1)

# Добавление в конец
my_list.append(100)  # O(1) амортизированная сложность

# Добавление в начало
my_list.insert(0, 100)  # O(n) - нужно сдвинуть все элементы

# Удаление из конца
my_list.pop()  # O(1)

# Удаление из начала
my_list.pop(0)  # O(n) - нужно сдвинуть все элементы

# Поиск элемента
100 in my_list  # O(n) - может проверить каждый элемент
my_list.index(100)  # O(n)

# Сортировка
my_list.sort()  # O(n log n) - Timsort алгоритм

Таблица сложностей для list

Амортизированная сложность append()

У append() есть тонкость — O(1) амортизированная сложность:

import time

my_list = []
start = time.perf_counter()

for i in range(1000000):
    my_list.append(i)
    if i in [1000, 10000, 100000, 1000000]:
        print(f"Элементы: {i:>7}, Список вмещает: {my_list.__sizeof__()} байт")

end = time.perf_counter()
print(f"Время: {end - start:.4f}s")

Потому что список не заново выделяет память при каждом append():

Структура роста списка:
Капацитет: 0 -> 1 -> 2 -> 4 -> 8 -> 16 -> 25 -> 35 -> 46 -> 58 -> ...
Элементов: 1    2    3    4    5    6     7     8     9    10

Рост примерно на 12% на каждое переполнение (CPython)

Поэтому в среднем (амортизированно) это O(1).

Практические примеры

Хорошо: O(1) операции

my_list = list(range(1000000))

# Быстро (O(1))
first = my_list[0]
last = my_list[-1]
middle = my_list[500000]

# Быстро (O(1))
my_list[0] = 999
my_list[500000] = 888
my_list.append(1000)

# Быстро (O(1))
my_list.pop()

Медленно: O(n) операции

# Медленно (O(n))
my_list.insert(0, 999)  # Сдвиг всех элементов
my_list.insert(500000, 888)  # Сдвиг половины элементов
my_list.pop(0)  # Сдвиг всех элементов
my_list.remove(500000)  # Поиск и сдвиг

# Медленно (O(n))
if 999999 in my_list:  # Полный поиск
    print("Found")

Сравнение со структурами данных

# Список — быстрый доступ, медленная вставка в начало
my_list = [1, 2, 3, 4, 5]
_ = my_list[0]  # O(1)
my_list.insert(0, 0)  # O(n)

# Deque — быстрая вставка с обеих сторон
from collections import deque
my_deque = deque([1, 2, 3, 4, 5])
_ = my_deque[0]  # O(1)
my_deque.appendleft(0)  # O(1)
my_deque.popleft()  # O(1)

# Dictionary — быстрый поиск по ключу
my_dict = {'key': 'value'}
my_dict['key']  # O(1)
'key' in my_dict  # O(1)

Изучение внутренней структуры

import sys

my_list = [1, 2, 3]
print(f"Размер объекта: {sys.getsizeof(my_list)} байт")
print(f"Capacity: {my_list.__sizeof__()}")
print(f"Length: {len(my_list)}")

# Смотрим адреса
print(f"ID списка: {id(my_list)}")
for i, item in enumerate(my_list):
    print(f"  item[{i}] (id={id(item)}): {item}")

Выводы

1. Чтение по индексу в Python списке — всегда O(1)
2. Это верно независимо от размера списка и позиции
3. Это одна из главных причин, почему списки полезны
4. Но вставка в начало — O(n), поэтому для этого лучше использовать deque
5. Поиск элемента — O(n), поэтому для частых поисков используй set или dict
6. Это сложность операции, а не сложность алгоритма для полного списка

Помни: когда говорят "чтение из списка O(1)" — имеют в виду доступ по индексу, а не поиск элемента!