O(n³) - Кубическая Сложность

Проблема

Умножение двух матриц размера n×n - естественная задача с тройной структурой: результат тоже n×n, и каждая из его n² ячеек требует своей собственной суммы из n произведений. Записать это напрямую - значит получить три вложенных цикла: по строкам, по столбцам, по элементам суммы. На матрицах 10×10 это 1000 операций - ничтожно мало. На 1000×1000 - уже миллиард, и разница между «мгновенно» и «минутами» здесь скрыта в третьем, самом незаметном уровне вложенности.

Решение

Алгоритм - O(n³), если в нём есть три вложенных цикла, и все три зависят от размера входа n. Узнать такой код можно, посчитав уровни вложенности: если убрать самый внутренний цикл, останется обычный O(n²) - именно третий уровень и делает из квадрата куб. Итоговое число операций - произведение n · n · n = n³, то есть каждый из n² «внешних» шагов дополнительно требует ещё n операций внутри.

Как это работает

Формально O(n³) означает: работа не превышает c · n³ для некоторой константы c, начиная с какого-то размера входа. У multiplyMatrices она ровно n³: n² ячеек результата, и на каждую - сумма из n произведений. Три вложенных цикла - структурный признак этого класса, так же как два вложенных давали O(n²) в материале про квадратичную сложность.

Числа растут гораздо резче, чем у O(n²). При n = 1 000 - ровно 1 000 000 000, один миллиард операций: на современном железе это уже секунды, а не миллисекунды. При n = 1 000 000 - 10¹⁸, квинтиллион: даже при миллиарде операций в секунду это заняло бы больше 31 года непрерывной работы. Данные выросли в 1000 раз, работа - в миллиард раз (1000³), а не в миллион, как было бы у O(n²).

Структурно причина - три цикла, вложенных друг в друга, и все три зависящие от n. У multiplyMatrices это i (строки), j (столбцы) и k (слагаемые суммы). Убрать любой один из трёх - и останется обычный O(n²): например, без внутреннего цикла k пришлось бы вычислять сумму как-то иначе, но перебор по i и j сам по себе даёт только квадрат.

O(n³) - не последнее слово даже для своей собственной классической задачи. Алгоритм Штрассена умножает матрицы за примерно O(n^2.807), находя в задаче структуру, которая позволяет обойтись без честного тройного перебора - тем же приёмом, что convex hull обходит наивный O(n²) в материале про O(n²) (только там речь была о геометрии точек, а не о числах в матрице). На практике наивный тройной цикл всё равно часто побеждает на небольших матрицах - у алгоритма Штрассена своя накладная расходность, которая окупается только на достаточно больших n.

Не всякая задача с O(n³) настолько повезёт с оптимизацией. Алгоритм Флойда-Уоршелла находит кратчайшие пути между всеми парами вершин графа за три вложенных цикла (промежуточная вершина, начало, конец), и для него, в отличие от умножения матриц, не существует настолько же быстрой альтернативы для общего случая - O(n³) здесь не наивность, а по сути неизбежная цена задачи.

Отличить O(n³) от O(n²) в code review проще всего простым подсчётом: сколько циклов вложены один в другой и все ли они зависят от одного и того же n. Третий уровень легко потерять из виду, особенно если он спрятан не в виде явного for, а внутри вызова другой O(n)-функции из уже вложенного дважды цикла - тот же приём, что превращает O(n) в O(n²) незаметно для автора, только на один уровень глубже.

Нюансы выбора

Маленькие и умеренные n - матрицы или таблицы примерно до нескольких сотен элементов в стороне, где секунды, а не минуты, остаются приемлемыми.

Задачи без известной более быстрой альтернативы - как у алгоритма Флойда-Уоршелла, где O(n³) - не наивность, а фактическая цена решения в общем случае.

Против более быстрых, но сложных альтернатив - если задача допускает алгоритм вроде Штрассена, переход на него оправдан только при достаточно больших n, иначе накладные расходы съедят выигрыш.

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

Примеры в коде

BLAS и LAPACK - стандартные библиотеки линейной алгебры не используют наивный тройной цикл напрямую, но именно от него отталкивались первые реализации умножения матриц, прежде чем появилась блочная и кэш-дружественная оптимизация.

Алгоритм Флойда-Уоршелла - в маршрутизации сетей и анализе графов находит кратчайшие расстояния между всеми парами узлов сразу, а не по одному, за счёт трёх вложенных циклов по вершинам.

Динамическое программирование с тремя измерениями - некоторые задачи (например, выравнивание нескольких последовательностей в биоинформатике) естественно требуют трёхмерной DP-таблицы, что и даёт O(n³) на её заполнение.

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

Когда применять

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

Примеры из практики

• Наивное умножение матриц - основа линейной алгебры и компьютерной графики, тройной цикл до появления оптимизированных библиотек вроде BLAS.
• Алгоритм Флойда-Уоршелла - поиск кратчайших путей между всеми парами вершин графа за три вложенных цикла по вершинам.