O(n^k) — Полиномиальная сложность

Определение

Полиномиальная сложность — это общий класс сложностей вида O(n^k), где k — константа больше 1.

Формула

$O(n^k)\text{, где }k\in \mathbb{N},k>1$

Примеры:

• O(n²) — квадратичная
• O(n³) — кубическая
• O(n⁴) — четвертой степени
• O(n⁵) — пятой степени

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

• Обобщенная форма для степенных сложностей
• Алгоритмы с полиномиальной сложностью считаются “эффективными”
• Класс сложности P (polynomial time)
• Вложенные циклы: k уровней вложенности = O(n

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

n	n²	n³	n⁴	n⁵
10	100	1,000	10,000	100,000
20	400	8,000	160,000	3,200,000
50	2,500	125,000	6,250,000	312,500,000

График сложности (логарифмическая шкала)

Операции (log₁₀)
       |
  10⁹  |                               ●  O(n⁵)
       |                             ●
  10⁶  |                         ● ●
       |                     ● ●  O(n⁴)
  10³  |                 ● ●
       |             ● ●  O(n³)
  100  |         ● ●
       |     ● ●  O(n²)
   10  | ● ●  O(n)
       |
    1  +---------------------------------------->
         10    20    50   100   200          n

Класс P vs NP

Класс P (Polynomial time):

• Задачи, решаемые за полиномиальное время
• O(n), O(n²), O(n³), O(n^100) и т.д.
• Считаются “эффективно решаемыми”

Класс NP:

• Задачи, решение которых можно проверить за полиномиальное время

P vs NP проблема: Открытый вопрос: равны ли классы P и NP? (P = NP?)

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

✅ Полиномиальные алгоритмы считаются “эффективными” ✅ Количество вложенных циклов ≈ степень полинома ❌ Высокие степени (k > 3) плохо масштабируются ❌ Не путать с экспоненциальной сложностью (O(2

Примеры кода

O(n⁴) - Четыре вложенных цикла

function fourNestedLoops(arr) {
  let count = 0;
  const n = arr.length;
 
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      for (let k = 0; k < n; k++) {
        for (let l = 0; l < n; l++) {
          count++;
        }
      }
    }
  }
 
  return count; // n⁴
}