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

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

Перебор списка имеет линейную сложность O(n), где n — количество элементов в списке.

Простой перебор — O(n)

# Самый простой случай: обход всех элементов один раз
def print_all_items(items):
    for item in items:
        print(item)  # Константная операция O(1)
    # Итого: O(n), где n = len(items)

# Или с индексом
def iterate_with_index(items):
    for i in range(len(items)):
        print(items[i])  # O(1) для доступа по индексу
    # Итого: O(n)

# Примеры:
items = [1, 2, 3, 4, 5]
print_all_items(items)  # 5 итераций

Вложенные циклы — O(n²)

# Два вложенных цикла — квадратичная сложность
def find_pairs(items):
    pairs = []
    for i in range(len(items)):           # n итераций
        for j in range(len(items)):       # n итераций
            if i != j:
                pairs.append((items[i], items[j]))
    return pairs
    # Итого: O(n * n) = O(n²)

# Пример: 5 элементов = 5 * 5 = 25 операций
items = [1, 2, 3, 4, 5]
find_pairs(items)  # 25 операций вместо 5

Три вложенных цикла — O(n³)

# Три вложенных цикла — кубическая сложность
def find_triplets(items):
    triplets = []
    for i in range(len(items)):              # n итераций
        for j in range(len(items)):          # n итераций
            for k in range(len(items)):      # n итераций
                if i != j and j != k and i != k:
                    triplets.append((items[i], items[j], items[k]))
    return triplets
    # Итого: O(n³)

# Пример: 5 элементов = 5 * 5 * 5 = 125 операций
items = [1, 2, 3, 4, 5]
find_triplets(items)  # 125 операций — очень медленно!

Сравнение сложности

import math

def analyze_complexity():
    sizes = [10, 100, 1000, 10000]
    
    for n in sizes:
        o_n = n
        o_n2 = n * n
        o_n3 = n * n * n
        o_log_n = int(math.log2(n)) if n > 0 else 0
        
        print(f"n={n:,}")
        print(f"  O(n)     = {o_n:,}")
        print(f"  O(log n) = {o_log_n}")
        print(f"  O(n²)    = {o_n2:,}")
        print(f"  O(n³)    = {o_n3:,}")
        print()

Поиск в неотсортированном списке — O(n)

# Линейный поиск: нужно проверить каждый элемент
def linear_search(items, target):
    for item in items:
        if item == target:
            return True
    return False

# Худший случай: элемент в конце или не существует
items = list(range(1000))
linear_search(items, 999)  # 999 сравнений в худшем случае

Поиск в отсортированном списке — O(log n)

# Двоичный поиск (бинарный поиск)
def binary_search(items, target):
    left, right = 0, len(items) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if items[mid] == target:
            return True
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

# Намного быстрее! Даже для 1000 элементов только ~10 операций
items = list(range(1000))
binary_search(items, 999)  # ~10 сравнений (log2(1000) ≈ 10)

# Или встроенный модуль
import bisect
bisect.bisect_left(items, 999)  # O(log n)

Таблица Big O сложностей

Простой перебор списка — O(n), но при вложенных циклах сложность растёт экспоненциально. Поэтому важно оптимизировать алгоритмы и использовать двоичный поиск для отсортированных данных.