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

Определение

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

Формула

$O(n^3)$

Характеристики

• Три вложенных цикла по n элементов
• Время растет кубически
• Очень плохо масштабируется
• Приемлемо только для очень малых данных

Куб данных

Представьте куб размером n×n×n:

n=2  -> куб 2×2×2 = 8 ячеек
n=3  -> куб 3×3×3 = 27 ячеек
n=4  -> куб 4×4×4 = 64 ячейки
n=5  -> куб 5×5×5 = 125 ячеек
n=10 -> куб 10×10×10 = 1000 ячеек

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

Размер (n)	n²	n³	Разница
10	100	1,000	10×
50	2,500	125,000	50×
100	10,000	1,000,000	100×
500	250,000	125,000,000	500×

График сложности

Операции (млн)
      |
 100  |                         ●  O(n³)
      |                       ●
  75  |                     ●
      |                   ●
  50  |                 ●
      |               ●
  25  |           ● ●
      |       ● ●
  10  |   ● ●  O(n²)
      | ●●
   0  +-------------------------------------->
        10   50  100  250  500  1000      n

Важно помнить

✅ Иногда можно оптимизировать до O(n²) ✅ Для матриц есть более быстрые алгоритмы ✅ Подходит только для малых данных (n < 500) ❌ Очень плохо масштабируется ❌ Часто есть более эффективные решения ❌ Три вложенных цикла — признак O(n³)

Примеры кода

1. Умножение матриц (наивный алгоритм)

function matrixMultiply(A, B) {
  const n = A.length;
  const result = Array(n).fill(0).map(() => Array(n).fill(0));
 
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        result[i][j] += A[i][k] * B[k][j];
      }
    }
  }
 
  return result;
}

2. Задача о трех суммах (3Sum)

function threeSum(nums, target) {
  const result = [];
  const n = nums.length;
 
  for (let i = 0; i < n - 2; i++) {
    for (let j = i + 1; j < n - 1; j++) {
      for (let k = j + 1; k < n; k++) {
        if (nums[i] + nums[j] + nums[k] === target) {
          result.push([nums[i], nums[j], nums[k]]);
        }
      }
    }
  }
 
  return result;
}