Основные сложности производительности, которые должен знать каждый программист, а также викторины в стиле интервью

Вдохновленный прошлыми страхами младшего разработчика, я решил написать пост, посвященный пугающей теме нотации Big O. Этот пост шаг за шагом раскрывает тему, обеспечивая вам удобство с концепциями. Кроме того, вы найдете вопросы викторины, чтобы проверить свое понимание. 🎯

Без лишних слов, давайте начнем!

Большой О

Большой O, также известный как нотация Big O,обеспечивает меру того, как производительность алгоритма масштабируется по мере увеличения размера входных данных, обычно обозначаемого как n. Он представляет собой наихудший сценарий использования алгоритмом времени выполнения или пространства. Упрощая и фокусируясь на общей эффективности, Big O позволяет нам понять производительность алгоритма, не углубляясь в особенности отдельных строк кода или вычислений.

При разработке алгоритмов и анализе их эффективности крайне важно понимать понятия времени и пространства сложности. Эти концепции помогают нам измерять производительность и масштабируемость нашего кода.

Существует шесть основных типов сложностей (время и пространство):

  • Константа: O(1)
  • Линейное время: O(n)
  • Линейное время: O(n log n)
  • Квадратичное время: O(n^2)
  • Экспоненциальное время: O(2^n)
  • Факторное время: O(n!)

Что такое временная сложность?

Временная сложность количественно определяет взаимосвязь между временем выполнения алгоритма и размером входных данных, с которыми он работает, независимо от типа машины, на которой он работает. Это помогает нам ответить на такие вопросы, как «Как растет время выполнения по мере роста входных данных?».
Другими словами, это функция размера входных данных.

Давайте рассмотрим некоторые из наиболее распространенных временных сложностей в зависимости от темпов их роста:

  • Постоянное время:O(1) — алгоритм занимает одинаковое количество времени независимо от размера входных данных. Например, доступ к элементу массива по индексу или определение четности числа.
function isEvenOrOdd(n) {
  return n % 2 ? 'Odd' : 'Even';
}
console.log(isEvenOrOdd(10)); // => Even
console.log(isEvenOrOdd(10001)); // => Odd
  • Логарифмическое время:O(log n) — время выполнения увеличивается логарифмически (с уменьшающейся скоростью) по мере увеличения размера входных данных. Распространен в алгоритмах «разделяй и властвуй», таких как бинарный поиск, которые делят отсортированный массив на основе целевого значения.
    В приведенном ниже примере размер входных данных уменьшается вдвое с каждой итерацией.
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // Found the target
    } else if (arr[mid] < target) {
      left = mid + 1; // Target is in the right half
    } else {
      right = mid - 1; // Target is in the left half
    }
  }

  return -1; // Target not found
}
  • Линейное время:O(n) — время выполнения увеличивается линейно с размером входных данных. Например, перебор массива.
    Используя один цикл, мы можем сказать, что наша функция выполняет O(n) операций, где n представляет длину входного массива.
function printAllElements(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}
  • Линейное время:O(n log n) — комбинация линейного времени O(n) и логарифмического времени O(log n). Время выполнения увеличивается пропорционально n, умноженному на логарифм n. Обычно используется в алгоритмах сортировки, таких как сортировка слиянием и быстрая сортировка.
function quicksort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quicksort(left), pivot, ...quicksort(right)];
}

В приведенном выше примере после рекурсивных вызовов (O(log n), поскольку вызовы выполняются на меньших подмассивах) функция объединяет отсортированный левый подмассив, опорный элемент и отсортированный правый подмассив. Эта операция конкатенации занимает линейное время (O(n)), так как включает копирование элементов в новый массив. В результате временная сложность алгоритма быстрой сортировки считается линейно-логической (O(n log n)).

  • Квадратичное время: O(n^2) — время выполнения увеличивается квадратично с размером входных данных. Часто встречается во вложенных циклах.
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]);
    }
  }
}
  • Полиномиальное время:O(n^k)(где k — константа больше 1, определяющая степень полинома).
    Алгоритм с полиномиальной временной сложностью обычно включает вложенные циклы или итерации, где число итераций увеличивается как степень входного размера.
  • Экспоненциальное время: O(2^n) — обычно ассоциируется с алгоритмами, включающими рекурсивное ветвление. Количество рекурсивных вызовов удваивается с каждым дополнительным элементом во входном массиве. В результате время выполнения увеличивается экспоненциально с размером входных данных, что приводит к значительному снижению производительности для больших входных данных.
// Example 1 -
// The number of operations doubles with each increase in the input size

const recursiveFibonacci = (n) => {
  if (n < 2) {
    return n;
  }
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};

console.log(recursiveFibonacci(6)); // 8
// Example 2 - 
function powerset(n = '') {
  const array = Array.from(n);
  const base = [''];

  const results = array.reduce((previous, element) => {
    const previousPlusElement = previous.map(el => {
      return `${el}${element}`;
    });
    return previous.concat(previousPlusElement);
  }, base);

  return results;
}

Во втором примере выше функция powerset генерирует набор всех различных комбинаций, которые могут быть сформированы с использованием элементов входного набора.

Для каждого элемента входной строки код удваивает количество сгенерированных подмножеств. Этот эффект удвоения обусловлен рекурсивным характером функции. Например, если входная строка содержит один элемент, код генерирует два подмножества (пустое множество и множество с этим элементом). Если входная строка состоит из двух элементов, код генерирует четыре подмножества (предыдущие два подмножества плюс еще два подмножества, включающие второй элемент).

  • Факторное время: O(n!) — время выполнения алгоритма экспоненциально растет с размером входных данных. Это происходит, когда алгоритму необходимо сгенерировать все возможные порядки или комбинации элементов. Это крайне неэффективно и быстро становится непрактичным даже при небольших размерах входных данных.
function getPermutations(string, prefix = '') {
  if(string.length <= 1) {
    return [prefix + string];
  }

  return Array.from(string).reduce((result, char, index) => {
    const reminder = string.slice(0, index) + string.slice(index+1);
    result = result.concat(getPermutations(reminder, prefix + char));
    return result;
  }, []);
}


getPermutations('ab') // ab, ba...
// n = 2, f(n) = 2;
getPermutations('abc') // abc, acb, bac, bca, cab, cba...
// n = 3, f(n) = 6;
getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd...
// n = 4, f(n) = 24;
getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde...
// n = 5, f(n) = 120;

Что такое космическая сложность?

Пространственная сложность относится к объему памяти, который требуется алгоритму, который определяется размером входных данных. Это помогает нам ответить на такие вопросы, как «Сколько дополнительной памяти необходимо для запуска алгоритма?».

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

  • Постоянное пространство: O(1) — алгоритм использует фиксированный объем памяти независимо от размера входных данных. Например, сохранение одной переменной.
function printNumber(n) {
  console.log(n);
}
  • Линейное пространство: O(n) — использование памяти линейно увеличивается с размером входных данных. Например, создание нового массива той же длины, что и вход.
function createArray(n) {
  const arr = [];
  for (let i = 0; i < n; i++) {
    arr.push(i);
  }
  return arr;
}
  • Квадратичное пространство: O(n^2) — использование памяти растет квадратично с размером входных данных. Распространен в алгоритмах, создающих матричные или вложенные структуры данных.
function createMatrix(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) {
    const row = [];
    for (let j = 0; j < n; j++) {
      row.push(i + j);
    }
    matrix.push(row);
  }
  return matrix;
}
  • Экспоненциальное пространство: O(2^n) — использование памяти экспоненциально растет с размером входных данных. Распространен в алгоритмах с рекурсивным ветвлением.
function generateSubsets(set) {
  const subsets = [];
  const generate = (currentSet, index) => {
    if (index === set.length) {
      subsets.push(currentSet);
      return;
    }
    generate(currentSet.concat(set[index]), index + 1);
    generate(currentSet, index + 1);
  };
  generate([], 0);
  return subsets;
}

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

Викторины с ответами

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

В каждом вопросе определите временную и пространственную сложность задействованных функций.

Вопрос 1:

function findSum(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — так как цикл проходит по массиву один раз.
Пространственная сложность:O(1) — поскольку единственная переменная sum используется дополнительная память.

Вопрос 2:

function hasDuplicateValues(arr) {
  const valueSet = new Set();
  for (let i = 0; i < arr.length; i++) {
    if (valueSet.has(arr[i])) {
      return true;
    }
    valueSet.add(arr[i]);
  }
  return false;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — так как он проходит через массив один раз, а операции Set имеют постоянное время.
Пространственная сложность: O(n) — поскольку Set setValueSet потенциально может хранить все уникальные значения из массива.

Вопрос 3:

function isSorted(arr) {
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < arr[i - 1]) {
      return false;
    }
  }
  return true;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — так как он выполняет итерацию по массиву один раз.
Пространственная сложность: O(1) — поскольку алгоритм использует память только для одна переменная, т.

Вопрос 4:

function findMaxValue(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — так как он выполняет итерацию по массиву один раз.

Пространственная сложность:O(1) — поскольку для отслеживания максимального значения используется только одна переменная (max).

Вопрос 5:

function factorial(n) {
  if (n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — поскольку рекурсия выполняет n умножений, общее количество операций растет линейно с размером входных данных.

Пространственная сложность: O(n) — рекурсивные вызовы создают стек вызовов с пространством, пропорциональным n.

Вопрос 6:

function fibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность:O(2^n) — экспоненциальная временная сложность, поскольку функция выполняет рекурсивные вызовы как для n — 1, так и для n — 2.
Пространственная сложность: O(n) — стек вызовов растет линейно с входом n.

Вопрос 7:

function mergeArrays(arr1, arr2) {
  return arr1.concat(arr2);
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(m + n) — линейная временная сложность, так как она объединяет два массива, где m и n — длины массивов.
Пространственная сложность: O(m + n) — сложность линейного пространства, так как создается новый массив с элементами из обоих входных массивов.

Вопрос 8:

function reverseString(str) {
  return str.split('').reverse().join('');
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — поскольку он преобразует строку в массив, переворачивает массив и снова соединяет его со строкой.
Пространственная сложность: O(n) — поскольку он создает массив символов во время операции разделения.

Вопрос 9:

function areAnagrams(str1, str2) {
  const sortedStr1 = str1.split('').sort().join('');
  const sortedStr2 = str2.split('').sort().join('');
  return sortedStr1 === sortedStr2;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n log n) — операция сортировки в коде имеет временную сложность в наихудшем случае [n log n], где n представляет длину входных строк.

  • Операция split(' ') имеет временную сложность O(n).
  • Временная сложность метода sort() обычно составляет * O(n log n).
  • Операция join(' ') имеет временную сложность O(n).

* Обычно используемые алгоритмы сортировки, такие как быстрая сортировка или сортировка слиянием, имеют среднюю временную сложность O(n log n).

Пространственная сложность: O(n) — поскольку он создает массивы для сортировки строк.

Вопрос 10:

function findIntersection(arr1, arr2) {
  const set1 = new Set(arr1);
  const intersection = [];
  for (let i = 0; i < arr2.length; i++) {
    if (set1.has(arr2[i])) {
      intersection.push(arr2[i]);
    }
  }
  return intersection;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n+m) — линейная временная сложность, так как она строит набор из arr1 и выполняет итерацию через arr2.

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

Следовательно, общая временная сложность определяется большим из двух массивов.

Пространственная сложность: O(m) /O(n) — линейная пространственная сложность, поскольку она создает набор с элементами из arr1 и массив для хранения пересечения.

  • Объемная сложность создания объекта Set из arr1 равна O(n), где n — длина arr1.
  • Пространственная сложность массива пересечений зависит от количества общих элементов, найденных между arr1 и arr2. В худшем случае либо n, либо m (длина arr2).
  • Другие переменные, используемые в коде (например, i и аргументы функции), имеют постоянные требования к пространству и не оказывают существенного влияния на общую сложность пространства.

Таким образом, общая пространственная сложность кода равна O(n), где n представляет собой длину большего массива между arr1 и arr2.

Вопрос 11:

function countDistinctElements(arr) {
  const distinctElements = new Set();
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      distinctElements.add(arr[i] + arr[j]);
    }
  }
  return distinctElements.size;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n²) — квадратичная временная сложность, так как есть вложенные циклы, повторяющиеся по входному массиву.
Пространственная сложность: O(n²) — квадратичная пространственная сложность, поскольку различные комбинации элементов хранятся в наборе.

Вопрос 12:

function findLongestSubstring(str) {
  let maxLength = 0;
  let start = 0;
  const charMap = new Map();
  
  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    
    if (charMap.has(char)) {
      start = Math.max(start, charMap.get(char) + 1);
    }
    
    maxLength = Math.max(maxLength, i - start + 1);
    charMap.set(char, i);
  }
  
  return maxLength;
}

🕐

🕓

🕙

Отвечать:

👀

Временная сложность: O(n) — линейная временная сложность, так как входная строка выполняется один раз, а операции внутри цикла выполняются за постоянное время.

Сложность пространства: O(min(n, m)) — линейная сложность пространства, где n — длина входной строки, а m — размер набора символов. Пространство, используемое charMap, не будет превышать размер набора символов.

  • Пространство, требуемое картой, зависит от количества уникальных символов в строке str, которое может быть не более min(n, m).
  • Пространственная сложность включает переменные maxLength, start и переменную цикла i, которые требуют постоянного объема памяти и не зависят от размера входных данных.

Поэтому, учитывая пространство, требуемое charMap, и дополнительные переменные, общая объемная сложность кода составляет O(min(n, m)).

Резюме

В этом посте мы рассмотрели важность анализа сложности времени и пространства. Анализ временной и пространственной сложности жизненно важен для эффективных алгоритмов и оптимизированного кода. Большая нотация O позволяет нам сравнивать и выражать эти сложности. Это помогает нам принимать обоснованные решения для повышения производительности и масштабируемости. Мы также рассмотрели несколько примеров, которые должны дать вам представление о том, как рассчитать время выполнения при разработке ваших проектов.

Я надеюсь, что вы нашли этот пост полезным. ✨
Следите за новостями! Если вы здесь впервые, не стесняйтесь изучать другие мои статьи и подписывайтесь на меня, чтобы получать обновления и более ценную информацию.

"Ресурс"