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

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

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

Почему O(1)?

my_list = [10, 20, 30, 40, 50]

# Все эти операции выполняются за O(1)
first = my_list[0]      # 10
middle = my_list[2]     # 30
last = my_list[4]       # 50
large_index = my_list[1000000]  # Займёт столько же времени!

Список в памяти — это непрерывный блок памяти. Когда вы обращаетесь к элементу по индексу, Python вычисляет адрес памяти по простой формуле:

адрес_элемента = базовый_адрес + индекс × размер_элемента

Этот расчёт занимает фиксированное время, независимо от того, какой индекс вы используете.

Как это работает на уровне памяти

# Python список в памяти выглядит примерно так:
# my_list = [10, 20, 30, 40, 50]
# 
# Память:
# адрес   содержимое
# 1000    10
# 1008    20
# 1016    30
# 1024    40
# 1032    50
#
# Размер одного элемента = 8 байт (для целых чисел в 64-бит системе)
#
# Получить элемент по индексу 2:
# адрес = 1000 + 2 × 8 = 1016
# Содержимое по адресу 1016 = 30

Этот расчёт выполняется один раз за O(1).

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

import time
from collections import deque

# Список - O(1)
my_list = list(range(1000000))
start = time.time()
for _ in range(1000):
    _ = my_list[500000]
print(f"Список: {time.time() - start:.6f} сек")

# Связный список (через deque, с приблизительной временной сложностью)
my_deque = deque(range(1000000))
start = time.time()
for _ in range(1000):
    # deque имеет O(n) доступ к середине
    value = my_deque[500000]
print(f"deque: {time.time() - start:.6f} сек")

# Словарь - O(1) в среднем
my_dict = {i: i*2 for i in range(1000000)}
start = time.time()
for _ in range(1000):
    _ = my_dict[500000]
print(f"Словарь: {time.time() - start:.6f} сек")

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

class PerformanceAnalysis:
    def __init__(self, size):
        self.list_data = list(range(size))
        self.dict_data = {i: i for i in range(size)}
    
    def access_list(self, index):
        """O(1) - время не зависит от размера списка"""
        return self.list_data[index]
    
    def access_dict(self, key):
        """O(1) в среднем - время не зависит от размера словаря"""
        return self.dict_data[key]
    
    def search_list(self, value):
        """O(n) - нужно проверить каждый элемент"""
        for item in self.list_data:
            if item == value:
                return True
        return False
    
    def linear_scan(self, start_index, end_index):
        """O(n) - где n = end_index - start_index"""
        result = 0
        for i in range(start_index, end_index):
            result += self.list_data[i]
        return result

# Использование
pa = PerformanceAnalysis(1000000)

# O(1) операции
print(pa.access_list(0))           # Быстро
print(pa.access_list(500000))      # Так же быстро!
print(pa.access_list(999999))      # Так же быстро!

# O(n) операция
print(pa.search_list(500000))      # Медленнее, так как может потребоваться сканирование

Амортизированная сложность добавления

Обращение к элементу — O(1), но добавление в конец списка — амортизированно O(1):

# Доступ - O(1)
my_list = [1, 2, 3, 4, 5]
print(my_list[2])  # O(1)

# Добавление в конец - амортизированно O(1)
my_list.append(6)  # O(1) в среднем
# Но иногда требуется переаллокация памяти (когда список заполнен)
# Это O(n), но происходит редко

# Вставка в начало или середину - O(n)
my_list.insert(0, 0)  # O(n) - нужно сдвинуть все элементы
my_list.insert(2, 2.5)  # O(n)

Всё дело в том, что Python использует динамический массив с резервом памяти. При добавлении нового элемента, если место есть, добавление занимает O(1). Если нет — Python выделяет новую память (обычно в 1.5-2 раза больше), копирует старые элементы (O(n)) и добавляет новый. Но так как переаллокация происходит редко, амортизированная сложность остаётся O(1).

Другие операции на списке

my_list = [10, 20, 30, 40, 50]

# O(1)
value = my_list[2]              # Доступ по индексу
my_list.append(60)              # Добавление в конец (амортизированно)

# O(n)
my_list.pop(0)                  # Удаление с начала (нужно сдвинуть элементы)
my_list.insert(0, 5)            # Вставка в начало (нужно сдвинуть элементы)
my_list.remove(20)              # Удаление по значению (сначала поиск O(n), потом сдвиг O(n))
my_list.pop()                   # Удаление с конца O(1)
index = my_list.index(30)       # Поиск O(n)

# O(n)
my_list_copy = my_list.copy()   # Копирование
reversed_list = my_list[::-1]   # Разворот

# O(n log n)
my_list.sort()                  # Сортировка

Почему это важно для производительности

# ❌ Плохо - O(n²)
result = []
for i in range(10000):
    result.insert(0, i)  # O(n) операция в цикле O(n)

# ✅ Хорошо - O(n)
result = []
for i in range(10000):
    result.append(i)  # O(1) операция в цикле O(n)
result.reverse()  # O(n) один раз в конце

# ✅ Лучше - O(n)
from collections import deque
result = deque()
for i in range(10000):
    result.appendleft(i)  # O(1) для deque в начало

Ключевые моменты

1. Доступ по индексу — O(1) благодаря непрерывности памяти
2. Размер списка не влияет на время доступа
3. Зато добавление/удаление в начале — O(n)
4. Выбирай структуру данных в зависимости от того, что тебе часто нужно делать
5. Профилируй код перед оптимизацией

Всё резюмируется просто: список в Python — это массив с O(1) доступом по индексу, что делает его очень эффективным для большинства случаев.