Join
Dmitriy D.
@boost
Алгоритмы
October 20, 2023

Оценка сложности алгоритма (Big O)

Способность оценить код с точки зрения эффективности алгоритма является одним из ключевых навыков хорошего программиста.

Сложность ваш враг. Каждый дурак может сделать что-то сложное,
тяжело сохранять сложные вещи простыми © Ричард Бренсон

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

Виды сложности

Константная O(1)

Количество операций не зависит от размера данных на вход, то есть алгоритм выполняется за постоянное время, например:

Cложение двух чисел

Имеет константную сложность, оно требует постоянное количество операций, независимо от того, насколько велики эти числа

function sum(a, b) {
   return a + b
}

Линейная O(n)

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

Сумма массива

Имеет линейную сложность, так как количество операций зависит от размера массива:

function array_sum(arr) {
   let sum = 0
   for (let number of arr) sum += number
   return sum
}

Cортировка вставками

Имеет линейную сложность, так как в каждую пару элементов массива необходимо выполнить вставку, и количество этих элементов пропорционально размеру входного массива

function insertionSort(arr) {  
   for (let i = 1; i < arr.length; i++) {
      let current = i;  
      while(arr[current - 1] !== undefined && compare(arr[current], arr[current - 1]) < 0) {  
         swap(arr, current - 1, current);  
         current--;  
      }  
   }
}

const compare = (value, wantedValue) => value - wantedValue
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]]

Квадратичная O(n²)

Сложность растет квадратично, то есть внутри итерации происходит еще одна итерация, например:

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

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

Сложность растет логарифмически, то есть для каждой итерации берется в два раза меньше элементов, например:

  • Бинарный поиск, в котором для нахождения элемента в отсортированном массиве, исходный массив циклично разделяется по центру

Неважная сложность

Вычисление наихудшего сценария может не учитывать рост более медленных сложностей, например:

O(N2 + N) = O(N2)
O(N + log n) = o(N)
O(5 * 2N + 10 * n100) = 2n

Тестирование

Любой алгоритм должен быть протестирован:

  • Тесты из условия
  • На общие случаи
  • На особые случаи

Сложение и умножение сложностей

Последовательные сложности складываются:

for (let num of arr) {
   console.log(num)
}

for (let num of arr) {
   console.log(num)
}

Сложность: 2N

Вложенные умножаются:

for (let a of arr) {
  for (let b of arr) {
    console.log(a + b)
  }
}

Сложность: 2*N

Сравнение

Скорость алгоритма

Имя                 Нотация      Оценка
--------------------------------------------
Константная         O(1)         Лучший
Логарифмическая     O(log N)     Круто
Линейная            O(N)         Хорошо
Линейная (лог.)     O(N log N)   Не очень
Полиномиальная      O(N ^ 2)     Плохо
Экспоненциальная    O(2 ^ N)     Фигово
Факториальная       O(N!)        Худший

Скорость операций

                         Доступ      Поиск       Вставка      Удаление
----------------------------------------------------------------------
Массив                   O(1)        O(N)        O(N)         O(N)
Связный список           O(N)        O(N)        O(1)         O(1)
Двоичное дерево поиска   O(log N)    O(log N)    O(log N)     O(log N)

или

                          Доступ     Поиск       Вставка      Удаление
----------------------------------------------------------------------
Массив                    Лучший     Хорошо      Хорошо       Хорошо
Связный список            Хорошо     Хорошо      Лучший       Лучший       
Двоичное дерево поиска    Круто      Круто       Круто        Круто

Вопросы

Какой код быстрее с точки зрения сложности алгоритма?

function findMinMax(arr) {
  let min = 0
  let max = 0

  for (let num of arr) {
    if (num < min) min = num
    if (num > max) max = num
  }
  
  // или
  
  for (let num of arr) {
    if (num < min) min = num
  }
  
  for (let num of arr) {
    if (num > max) max = num
  }
  
  return [min, max];
}

Какая сложность вставки ключа в объект?

  • Константная

Полезное

Видео

Материалы

October 20, 2023, 15:42
0 views
0 reactions