Какой алгоритм лучше, а какой хуже?

Как можно сравнить 2 функции или алгоритма, выполняющие одну задачу, но имеющие разную реализацию между собой?

Зачем спрашивают

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

Ответ

Коротко: Критерии оценки алгоритмов:

Time complexity

Space complexity

В редких случаях — стабильность алгоритма (например, для сортировок)

Выражаются или описываются big O нотацией.

Подробнее:

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

Пример:


function sumArray(arr) {
  let sum = 0;            // O(1) по памяти
  for (let i = 0; i < arr.length; i++) { // O(n) по времени
    sum += arr[i];
  }
  return sum;
}

Time complexity = O(n) (цикл по каждому элементу).

Space complexity = O(1) (используем только одну переменную sum).

Обе оценки выражаются через Big O, но они разные по смыслу.

Компромиссы

Big O описывает верхнюю границу роста функции. На практике чаще всего анализируют худший случай, но иногда используют и средний, и лучший

Нужно смотреть не только теорию, но и профилировать код на практике.

Встречные вопросы

Big O всегда только про скорость выполнения?

Приведите примеры часто встречающихся сложностей

В нотации, например, O(n), что такой O? Что такоe n?

Для чего измеряются стабильность алгоритма?

Красные флаги

Ответ без объяснения («Ну это просто big O»).

Сравнение только по скорости без упоминания памяти.

Сравнение по «читабельности» кода (сигнал, что человек не понимает алгоритмы)

Практика

Задача 1


// Какая сложность по времени и памяти? И почему?

function sumArray(arr) {
  let sum = 0;
  
  for (const item of arr) {
    sum += item;
  }
  
  return sum;
}

Задача 2


// Какая сложность по времени и памяти? И почему?
// Можно ли улучшить результат?

function contains(arr, target) {
  for (const item of arr) {
    if (item === target) return true;
  }
  
  return false;
}

Задача 3


// Какая сложность по времени и памяти? И почему?

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

Задача 4


// Какая сложность по времени и памяти? И почему?

function removeDuplicates(arr) {
  return [...new Set(arr)];
}

Задача 5


// Написать проверяющую функцию, есть ли в массиве два числа, сумма которых равна target
// Целевая сложность -- O(n)

function hasPairWithSum(arr, target) {
  return false;
}

Источники / ссылки

Big O Cheat Sheet