Какая будет сложность, если перебирать цикл в цикле?

Временная сложность вложенных циклов

Вложенные циклы кардинально увеличивают временную сложность алгоритма. Вместо линейного роста O(n) получается полиномиальный рост, чаще всего O(n²).

Базовый принцип

Умножение итераций

• Внешний цикл выполняется N раз
• На каждую итерацию внешнего цикла внутренний цикл выполняется M раз
• Итого: N × M операций

# Простой пример: два цикла одного размера
n = 1000
for i in range(n):           # Выполняется n раз
    for j in range(n):       # Выполняется n раз на каждой итерации i
        print(i, j)          # Всего n * n = n² = 1,000,000 итераций

Сложность: O(n²) — квадратичная

Варианты сложности вложенных циклов

Два цикла одного размера → O(n²)

for i in range(n):           # O(n)
    for j in range(n):       # O(n)
        operation()          # O(1)
# Итого: n * n = O(n²)

Два цикла разного размера → O(n·m)

for i in range(n):           # O(n)
    for j in range(m):       # O(m)
        operation()          # O(1)
# Итого: n * m = O(n·m)

Внутренний цикл меньше внешнего → O(n²)

for i in range(n):           # O(n)
    for j in range(i):       # O(i), в среднем O(n/2)
        operation()          # O(1)
# Итого: n/2 * n = O(n²) — всё ещё квадратичная!
sum = 1 + 2 + 3 + ... + n = n(n+1)/2 ≈ n²/2

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

for i in range(n):           # O(n)
    for j in range(n):       # O(n)
        for k in range(n):   # O(n)
            operation()      # O(1)
# Итого: n * n * n = O(n³) — кубическая сложность!

Практический пример: сортировка пузырьком

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # Внешний цикл: O(n)
        for j in range(n - 1):   # Внутренний цикл: O(n)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Сложность: O(n²)
# Для массива из 1000 элементов: ~1,000,000 сравнений
# Для массива из 10,000 элементов: ~100,000,000 сравнений

Отличие от последовательных циклов

❌ Неправильно путать вложенные с последовательными

# Последовательные циклы → O(n + m) ≈ O(n)
for i in range(n):    # O(n)
    print(i)
for j in range(m):    # O(m)
    print(j)
# Итого: n + m = O(n + m) — ЛИНЕЙНАЯ, не квадратичная!

# Вложенные циклы → O(n * m)
for i in range(n):    # O(n)
    for j in range(m):  # O(m) на каждую итерацию i
        print(i, j)
# Итого: n * m = O(n * m) — КВАДРАТИЧНАЯ

Вычисление сложности вложенных циклов

Алгоритм анализа

1. Определить, сколько раз выполняется каждый цикл
2. Умножить количества итераций
3. Упростить выражение, оставив старший порядок

# Пример 1: Простая вложенность
for i in range(5):          # 5 раз
    for j in range(5):      # 5 раз на каждой итерации i
        operation()         # O(1)
# Всего: 5 * 5 = 25 операций

# Пример 2: Зависимое количество итераций
for i in range(10):         # 10 раз
    for j in range(i):      # 0, 1, 2, 3, ..., 9 раз
        operation()         # O(1)
# Всего: 0 + 1 + 2 + ... + 9 = 45 операций
# Формула: n(n-1)/2 ≈ O(n²)

Реальные примеры из алгоритмов

O(n²) алгоритмы

• Сортировка пузырьком, вставками, выбором
• Поиск пары элементов (two-pointer problems)
• Все с все сравнения в матрице

# Поиск всех пар в массиве
for i in range(n):
    for j in range(i + 1, n):  # Оптимизация: j начинается с i+1
        # Проверка пары (arr[i], arr[j])
        if arr[i] + arr[j] == target:
            print(i, j)
# Сложность: O(n²), но константа 1/2 меньше

O(n³) алгоритмы

• Умножение матриц (наивный алгоритм)
• Поиск всех троек элементов

# Умножение матриц
result = [[0] * n for _ in range(n)]
for i in range(n):      # O(n)
    for j in range(n):  # O(n)
        for k in range(n):  # O(n)
            result[i][j] += A[i][k] * B[k][j]
# Сложность: O(n³)

Сравнение производительности

Когда n растёт, сложность O(n²) и O(n³) становятся неприемлемы!

Оптимизация вложенных циклов

Техника: используй структуры данных вместо циклов

# ❌ Медленно: O(n²)
for num in arr1:
    for other in arr2:
        if num == other:
            count += 1

# ✅ Быстро: O(n + m) благодаря set
set1 = set(arr1)  # O(n)
for num in arr2:  # O(m)
    if num in set1:  # O(1)
        count += 1
# Итого: O(n + m), а не O(n * m)!

Техника: ранее завершение

# Если внутренний цикл может завершиться раньше
for i in range(n):
    for j in range(i + 1, n):
        if condition:
            break  # Ранее выхода может помочь на практике
# Сложность остаётся O(n²) в худшем случае, но быстрее на практике

Вложенные циклы — это одна из главных причин неэффективных алгоритмов. Всегда старайся избежать их, если возможно, используя более умные структуры данных!