Глава 6. Навык #3: Алгоритмическое мышление

"AI может написать алгоритм. Но понимать, почему он медленный или быстрый — ваша задача."

6.1. Понимание сложности и оптимизации

Зачем нужно алгоритмическое мышление с AI

Сценарий:

AI сгенерировал функцию для поиска дубликатов в списке:

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

Код работает!

Тестируем:

• 10 элементов → 0.001 секунды ✅
• 100 элементов → 0.1 секунды ✅
• 1000 элементов → 10 секунд ⚠️
• 10,000 элементов → 17 минут! ❌

Что случилось?

Без понимания сложности алгоритма вы не заметите проблему до продакшна.

Что такое сложность алгоритма

Сложность — это ответ на вопрос: "Как меняется время выполнения при росте данных?"

Обозначение: Big O notation (О-большое)

Примеры:

• O(1) — константное время (не зависит от размера данных)
• O(n) — линейное время (время растёт пропорционально данным)
• O(n²) — квадратичное время (время растёт квадратично)
• O(log n) — логарифмическое время (очень эффективно)

Визуализация

Время выполнения для разного n:

n = 10      n = 100     n = 1000    n = 10,000
-----------------------------------------------
O(1)      | 1 мс      | 1 мс      | 1 мс      | 1 мс
O(log n)  | 3 мс      | 7 мс      | 10 мс     | 13 мс
O(n)      | 10 мс     | 100 мс    | 1 сек     | 10 сек
O(n²)     | 100 мс    | 10 сек    | 17 мин    | 28 часов!

Вывод: Разница между O(n) и O(n²) огромна для больших данных!

6.2. Big O notation

O(1) — Константное время

Описание: Время не зависит от размера входных данных.

Пример:

def get_first_element(arr):
    return arr[0]  # Всегда одна операция

# n = 10 → 1 операция
# n = 1,000,000 → 1 операция

Другие примеры:

• Доступ к элементу массива по индексу: arr[5]
• Доступ к значению в словаре: dict['key']
• Добавление в конец списка: arr.append(x) (амортизированное)

O(n) — Линейное время

Описание: Время растёт пропорционально размеру данных.

Пример:

def find_max(arr):
    max_val = arr[0]
    for item in arr:  # Проходим весь массив
        if item > max_val:
            max_val = item
    return max_val

# n = 10 → 10 операций
# n = 1000 → 1000 операций

Другие примеры:

• Поиск элемента в неотсортированном списке
• Сумма всех элементов
• Вывод всех элементов

O(n²) — Квадратичное время

Описание: Время растёт квадратично (вложенные циклы).

Пример:

def has_duplicates(arr):
    for i in range(len(arr)):           # n итераций
        for j in range(i + 1, len(arr)): # n итераций для каждого i
            if arr[i] == arr[j]:
                return True
    return False

# n = 10 → ~100 операций
# n = 100 → ~10,000 операций
# n = 1000 → ~1,000,000 операций

Проблема: Становится очень медленным для больших данных!

O(log n) — Логарифмическое время

Описание: Очень эффективно. Делим задачу пополам на каждом шаге.

Пример: Бинарный поиск

def binary_search(sorted_arr, target):
    left, right = 0, len(sorted_arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            left = mid + 1  # Ищем в правой половине
        else:
            right = mid - 1  # Ищем в левой половине

    return -1

# n = 1000 → ~10 операций
# n = 1,000,000 → ~20 операций

Почему быстро:

• На каждом шаге отбрасываем половину данных
• 1,000,000 → 500,000 → 250,000 → ... → 1 (всего ~20 шагов)

O(n log n) — Эффективная сортировка

Описание: Лучшие алгоритмы сортировки.

Примеры:

• Merge Sort
• Quick Sort
• Heap Sort

# Встроенная сортировка в Python — O(n log n)
sorted_arr = sorted(arr)

6.3. Базовые алгоритмы: сортировка и поиск

Сортировка

Bubble Sort — O(n²) (медленно)

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Когда использовать: Почти никогда (учебный пример).

Quick Sort — O(n log n) в среднем (быстро)

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)

Когда использовать: Общего назначения сортировка.

В реальности

Просто используйте встроенную сортировку:

# Python
sorted_arr = sorted(arr)  # O(n log n)
arr.sort()                # O(n log n), in-place

# JavaScript
arr.sort((a, b) => a - b)

С AI:

AI, отсортируй массив

AI сгенерирует sorted(arr) — правильное решение!

Поиск

Линейный поиск — O(n)

def linear_search(arr, target):
    for i, item in enumerate(arr):
        if item == target:
            return i
    return -1

Когда использовать: Для небольших или неотсортированных данных.

Бинарный поиск — O(log n)

def binary_search(sorted_arr, target):
    left, right = 0, len(sorted_arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Когда использовать: Для отсортированных данных (в 100-1000 раз быстрее линейного!).

Важно: Массив должен быть отсортирован!

6.4. Рекурсия и итерация

Рекурсия

Описание: Функция вызывает сама себя.

Пример: Факториал

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

# factorial(5) = 5 * factorial(4)
#              = 5 * 4 * factorial(3)
#              = 5 * 4 * 3 * factorial(2)
#              = 5 * 4 * 3 * 2 * factorial(1)
#              = 5 * 4 * 3 * 2 * 1 = 120

Когда использовать:

• Задачи, естественно описываемые рекурсией (обход дерева, Fibonacci)
• Когда код становится проще и понятнее

Осторожно:

• Глубокая рекурсия → переполнение стека (stack overflow)
• Python: лимит ~1000 вызовов

Итерация

Описание: Использование циклов.

Тот же факториал итеративно:

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

Когда использовать:

• Для больших n (нет риска переполнения стека)
• Часто эффективнее по памяти

Выбор: рекурсия или итерация?

Рекурсия:

• ✅ Код проще и понятнее
• ❌ Риск переполнения стека
• ❌ Медленнее (вызовы функций дороги)

Итерация:

• ✅ Эффективнее
• ✅ Нет риска переполнения
• ❌ Иногда сложнее читается

С AI: AI может предложить оба варианта. Вы выбираете подходящий.

6.5. Структуры данных: когда использовать что

Массив / Список

Описание: Упорядоченная коллекция элементов.

arr = [1, 2, 3, 4, 5]

Операции:

• Доступ по индексу: O(1) → arr[2]
• Поиск элемента: O(n) → 3 in arr
• Добавление в конец: O(1) → arr.append(6)
• Вставка в середину: O(n) → arr.insert(2, 99)

Когда использовать:

• Нужен порядок элементов
• Частый доступ по индексу
• Добавление в конец

Словарь / Хеш-таблица

Описание: Ключ-значение пары.

user = {"name": "Шахруз", "age": 40}

Операции:

• Доступ по ключу: O(1) → user["name"]
• Добавление: O(1) → user["city"] = "Ташкент"
• Поиск ключа: O(1) → "age" in user

Когда использовать:

• Нужен быстрый доступ по ключу
• Не важен порядок

Критично важно:

Сравните:

# Плохо: O(n)
def find_user_by_id(users_list, user_id):
    for user in users_list:
        if user['id'] == user_id:
            return user
    return None

# Хорошо: O(1)
users_dict = {user['id']: user for user in users_list}

def find_user_by_id(user_id):
    return users_dict.get(user_id)

Разница: В 1000 раз быстрее для больших данных!

Множество / Set

Описание: Неупорядоченная коллекция уникальных элементов.

numbers = {1, 2, 3, 4}

Операции:

• Проверка наличия: O(1) → 3 in numbers
• Добавление: O(1) → numbers.add(5)
• Удаление дубликатов: O(n) → set([1, 1, 2, 2, 3])

Когда использовать:

• Нужны уникальные элементы
• Частая проверка наличия элемента

Пример: оптимизация проверки дубликатов

# Плохо: O(n²)
def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# Хорошо: O(n)
def has_duplicates(items):
    return len(items) != len(set(items))

6.6. Практика: решение задач с AI

Задача 1: Найти два числа, которые в сумме дают target

Условие:

# Дан массив чисел и target
nums = [2, 7, 11, 15]
target = 9

# Найти индексы двух чисел, которые в сумме дают target
# Ответ: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)

Решение 1: Брутфорс — O(n²)

def two_sum(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Решение 2: Хеш-таблица — O(n)

def two_sum(nums, target):
    seen = {}  # {число: индекс}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in seen:
            return [seen[complement], i]

        seen[num] = i

    return []

С AI:

AI, реши задачу two sum.
Оптимизируй для O(n) сложности.

AI, скорее всего, предложит решение с хеш-таблицей.

Ваша задача: Понять, почему это O(n), а не O(n²).

Задача 2: Палиндром

Условие: Проверить, является ли строка палиндромом.

is_palindrome("racecar")  # True
is_palindrome("hello")    # False

Решение 1: Реверс строки

def is_palindrome(s):
    return s == s[::-1]

Сложность: O(n)

Решение 2: Два указателя

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

Сложность: O(n), но эффективнее по памяти (не создаём копию строки).

6.7. Олимпиадный опыт автора

Коллекционирование задачек

В школьные годы (7-11 класс) я коллекционировал задачки.

Не просто решал — коллекционировал.

Зачем?

Потому что олимпиадные задачи часто повторяют паттерны.

Если вы видели 100 задач на динамическое программирование, вы узнаете 101-ю.

Библиотеки решений

Я собирал библиотеки типовых решений:

• Алгоритмы сортировки
• Поиск в глубину (DFS) и ширину (BFS)
• Динамическое программирование
• Жадные алгоритмы
• Структуры данных (стеки, очереди, деревья)

На олимпиаде:

Вместо того, чтобы писать алгоритм с нуля, я адаптировал шаблон из библиотеки.

Это и есть то, что делает AI сейчас!

AI имеет огромную "библиотеку" паттернов. Вы формулируете задачу, AI адаптирует паттерн.

Урок для AI-разработчика

Раньше: Вы собирали библиотеку решений в голове

Сейчас: AI — это ваша библиотека. Но вы должны:

• Узнать паттерн (понять, какой тип задачи)
• Сформулировать запрос (промпт)
• Проверить решение (понять сложность)

6.8. Упражнения

Задание 1: Анализ сложности

AI сгенерировал следующий код:

def find_pairs(arr, target):
    pairs = []
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i] + arr[j] == target:
                pairs.append((i, j))
    return pairs

Вопросы:

1. Какая сложность алгоритма?
2. Есть ли проблемы с этим кодом?
3. Как оптимизировать?

Задание 2: Выбор структуры данных

Для каждого случая выберите подходящую структуру данных:

1. Хранить имена уникальных пользователей
2. Хранить очередь задач (FIFO - first in, first out)
3. Хранить историю браузера (последнее действие - первым удаляется)
4. Быстрый поиск пользователя по ID

Задание 3: Оптимизация с AI

Попросите AI решить задачу: "Найти наибольший элемент в массиве"

Затем:

1. Проанализируйте сложность решения
2. Попросите AI оптимизировать
3. Сравните решения

Ключевые выводы главы

✅ Сложность критична: Разница между O(n) и O(n²) огромна

✅ Big O notation: O(1), O(log n), O(n), O(n log n), O(n²)

✅ Выбор структуры данных: Список vs Словарь vs Множество

✅ AI генерирует, вы анализируете: AI может дать O(n²), когда нужно O(n)

✅ Паттерны решений: Как олимпиадные библиотеки, AI знает паттерны

✅ Практика важна: Решайте задачи на LeetCode с AI, но понимайте решения

✅ С AI: Формулируйте требования к сложности: "Оптимизируй для O(n)"

Следующая глава: Формулирование задач — core skill для работы с AI