В поисках O(n): как научиться видеть эффективные решения задач

2026-02-13 в 11:16, admin, рубрики: алгоритм, линейная скорость, обучение программированию, разбор задач, сложность алгоритма

Привет! Сегодня разберём простую на первый взгляд, но очень показательную задачку: найти максимальное произведение двух чисел в массиве целых чисел.

На собеседованиях, в олимпиадах или даже в реальных задачах часто возникают простые на вид задачи, за которыми скрывается важный урок: правильный выбор алгоритма решает всё.

Казалось бы — что сложного скрывает поставленная задача о нахождении максимального произведения двух чисел? Но в зависимости от подхода решение может работать за O(n^2), O(n log n) или O(n).

В поисках O(n): как научиться видеть эффективные решения задач - 1

С этой задачей я столкнулся на своём первом собеседовании и предложил не самое оптимальное решение.

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

Постановка задачи

Дан массив целых чисел (может содержать положительные, отрицательные и нули, количество элементов не менее 1). Нужно найти максимальное возможное произведение двух различных элементов (обычно подразумевается, что индексы разные, но значения могут совпадать).

Базовое решение или как делать не надо (O(n²))

Начнём с самого прямолинейного подхода: проверим все возможные пары элементов и выберем ту, чьё произведение максимально.

Почему это работает? Потому что мы не упускаем ни одного кандидата. Даже если в массиве спрятаны два огромных по модулю отрицательных числа, мы их обязательно рассмотрим.

Как именно перебирать пары?

Чтобы не дублировать комбинации (например, и ), будем перебирать только пары с :

идёт от до
идёт от до

Так мы рассмотрим ровно уникальных пар — это и есть квадратичная сложность или .

✅ Преимущества

Простота
Надёжность: не зависит от знаков, нулей, порядка — работает всегда.
Лёгкость тестирования: легко проверить на маленьких примерах вручную.

❌ Недостатки

Скорость: при n = — уже ~ миллионов операций, исполнение которых может занять секунды. При n = — ~ миллиардов пар, задача выйдет за пределы Time Limit на большинстве платформ.
Не масштабируется: даже если процессор станет в 10 раз быстрее — вы выиграете лишь в константе, а не в асимптотике.

Реализация на Python под катом

def max_product(arr):
    n = len(arr)
    if n < 2:
        return -1
    
    max_prod = arr[0] * arr[1]
    # либо max_prod = arr[0] - по сути, вкусовщина
    for i in range(n):
        for j in range(i + 1, n):
            product = arr[i] * arr[j]
            if product > max_prod:
                max_prod = product
                
    return max_prod

Компромиссное решение (O(n log n))

Перебор всех пар - это решение слишком «в лоб», давайте подумаем: где вообще может лежать ответ?

Заметим важную вещь: Максимальное произведение двух чисел в массиве — это

либо произведение двух самых больших чисел
либо произведение двух самых маленьких (т.е. самых отрицательных) чисел

Следовательно, нам не нужно проверять все пары — достаточно рассмотреть только две кандидатные пары: 2 максимальных числа, либо 2 минимальных числа, и выбрать максимальное из их произведений.

Такое умозаключение наталкивает нас на идею сортировки массива и рассмотрении крайних 2 чисел с каждого конца. Сортировка выполняется за O(n log n), рассмотрение двух произведений - O(1), поэтому итоговая сложность алгоритма будет O(n log n)

✅ Преимущества

Очень легко понять и написать — идеально для собеседования.
Работает быстро даже для миллионов объектов.
Минимум логики — всего два сравнения после сортировки.

❌ Недостатки

Сложность O(n log n) — проигрывает линейному решению на больших данных.
Изменяет исходный массив

Реализация на Python под катом

def max_product(arr):
    if len(arr) < 2:
        return -1
    
    arr.sort()    
    # Два кандидата:
    product_of_largest = arr[-1] * arr[-2]   # самые большие
    product_of_smallest = arr[0] * arr[1]    # самые маленькие
    
    return max(product_of_largest, product_of_smallest)

Оптимальное решение (O(n))

Если мы уже поняли, что максимальное произведение — это максимум из двух кандидатов:

два самых больших числа,
два самых маленьких числа,

то зачем вообще сортировать весь массив? Ведь нам нужны только четыре числа: два максимума и два минимума.

Их можно найти за один проход, не трогая остальные элементы.

Это классический приём: поддерживать текущие экстремумы, обновляя их при просмотре каждого элемента «на лету».

Идея алгоритма

Будем отслеживать:

max1, max2 — два наибольших числа (max1 ≥ max2)
min1, min2 — два наименьших числа (min1 ≤ min2)

Проходим по массиву один раз. Для каждого элемента x:

Если x > max1 → max2 = max1, max1 = x
- Иначе если x > max2 → max2 = x
Если x < min1 → min2 = min1, min1 = x
- Иначе если x < min2 → min2 = x

В конце возвращаем max(max1 max2, min1 min2).

✅ Преимущества

Оптимальная временная сложность: O(n) — один проход.
Постоянная память: O(1) — только четыре переменные.
Не изменяет исходный массив — безопасен для дальнейшего использования.
Масштабируется: работает быстро даже для миллиарда объектов.

Реализация на Python под катом

def max_product_linear(arr):
    if len(arr) < 2:
       return -1
    
    # Инициализируем экстремумы первыми двумя элементами
    if arr[0] > arr[1]:
        max1, max2 = arr[0], arr[1]
        min1, min2 = arr[1], arr[0]
    else:
        max1, max2 = arr[1], arr[0]
        min1, min2 = arr[0], arr[1]
    
    # Проходим по оставшимся элементам
    for i in range(2, len(arr)):
        x = arr[i]
        
        # Обновляем максимумы
        if x > max1:
            max2 = max1
            max1 = x
        elif x > max2:
            max2 = x
        
        # Обновляем минимумы
        if x < min1:
            min2 = min1
            min1 = x
        elif x < min2:
            min2 = x
    
    return max(max1 * max2, min1 * min2)

Это решение демонстрирует важный принцип:
Не нужно сортировать, если нужны только экстремумы.
Именно такие «мелкие оптимизации» часто отличают хорошего разработчика — того, кто не просто решает задачу, а думает о ресурсах.

P.S.

Почему так важно всегда помнить про сложность даже простого алгоритма?
На этом графике изображены сложности представленных решений, а конкретно, рост времени выполнения задачи в зависимости от размера входного массива. Первое решение сразу выбивается из колеи, говоря нам о том, что его лучше не использовать на практике.

Сравнение 3-х решений - RunningTime(N), где N - размер массива

Если рассматривать оставшиеся 2 решения, то, казалось бы, графики времени выполнения «почти совпадают», но нельзя не принимать во внимание тот факт, что в большинстве реальных задач размеры входных данных куда больше 20, чем ограничивается ось абсцисс на графике. Давайте будем реалистами и возьмём массив размера хоть сколько‑то приближенного к возможной реальной задачи:

Вы разрабатываете систему оповещения для умного дома. У вас есть данные за месяц наблюдений с интервалом в 5 минут — это более 8000 измерений отклонений температуры от нормы (например, −3°, +5°, −7° и т.д.). Чтобы оценить риск термического стресса для оборудования, инженеры предложили метрику: «наибольшее возможное совместное отклонение» — то есть максимальное произведение двух отклонений. Почему? Потому что два сильных отрицательных скачка (например, −8 и −6) дают положительный вклад в износ системы, как и два сильных положительных (+7 и +5).