Алгоритмы на JavaScript с наглядными примерами
Полная дорожная карта React
26.01.2022
33 понятия, которые должен знать каждый разработчик JavaScript
27.01.2022Большинство из нас боятся алгоритмов и даже не начинают их изучать. Но вы не должны бояться. Алгоритм — это всего лишь шаги для решения проблемы.
Рассмотрим основные алгоритмы простым и наглядным образом.
Не пытайтесь запомнить их, алгоритм больше касается решения проблем. Выписывайте для себя важные моменты.
- Обозначение большого O
- Алгоритмы
Понимание нотации Big O
Нотация Big O — это способ представить временную и пространственную сложность алгоритма.
- Сложность времени: время, необходимое алгоритму для завершения выполнения.
- Пространственная сложность: память, занимаемая алгоритмом.
Существует несколько выражений (обозначений), которые представляют временную сложность алгоритма.
- O(1): Постоянная временная сложность. Это идеальный случай.
- O(log n): логарифмическая временная сложность. Если
log(n) = xтогда это то же самое, что10^x - O(n): линейная временная сложность. Время увеличивается с количеством входных данных линейным образом. Например, если один вход занимает 1 мс, 4 входа потребуют 4 мс для выполнения алгоритма.
- O (n ^ 2): квадратичная временная сложность. В основном это происходит в случае вложенных циклов.
- O(n!): Факторная временная сложность. Это наихудший сценарий, которого следует избегать.
Вы должны попытаться написать свой алгоритм так, чтобы он мог быть представлен первыми тремя обозначениями. И последних двух следует избегать как можно чаще.
Вы хотите, чтобы ваша сложность была как можно более низкой и прямой, в идеале избегая всего, что превышает O (n).
В дальнейших разделах этой статьи вы увидите примеры каждой нотации. Пока это все, что вам нужно знать.
Алгоритм
Что такое алгоритм и зачем беспокоиться?
Способ решения проблемы или, можно сказать, шаги , процедура или набор правил для решения проблемы известен как алгоритм.Пример: Алгоритм поисковой системы для получения данных, относящихся к поисковой строке.
Как программист вы столкнетесь со многими проблемами, которые необходимо решить с помощью этих алгоритмов. Так что лучше, если вы их уже знаете.
Рекурсия
Функция, вызывающая саму себя, является рекурсией. Думайте об этом как об альтернативе циклу.
|
1 2 3 4 5 6 7 8 9 |
function recursiveFn() { console.log("This is a recursive function"); recursiveFn(); } recursiveFn(); |
В приведенном выше фрагменте посмотрите на строку 3, где recursiveFn вызывается в самом recursiveFn. Как упоминалось ранее, рекурсия — это альтернатива циклу.
Итак, сколько раз эта функция будет выполняться?
Ну, это создаст бесконечный цикл, потому что его ничто не остановит в любой момент.
Допустим, нам нужно запустить цикл всего 10 раз. На 11-й итерации функция должна вернуться. Это остановит цикл.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
let count = 1; function recursiveFn() { console.log(`Recursive ${count}`); if (count === 10) return; count++; recursiveFn(); } recursiveFn(); |
В приведенном выше фрагменте строка 4 возвращается и останавливает цикл на счете 10.
Теперь давайте посмотрим на более реалистичный пример. Наша задача — вернуть массив нечетных чисел из заданного массива. Этого можно добиться несколькими способами, включая цикл for, метод Array.filter и т. д.
Но чтобы продемонстрировать использование рекурсии, я буду использовать функцию helperRecursive.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function oddArray(arr) { let result = []; function helperRecursiveFn(arr) { if(arr.length === 0) { return; // 1 } else if(arr[0] % 2 !== 0) { result.push(arr[0]); // 2 } helperRecursiveFn(arr.slice(1)); // 3 } helperRecursiveFn(arr); return result; } oddArray([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); // OutPut -> [1, 3, 5, 7, 9] |
Здесь рекурсивной функцией является helperRecursiveFn.
- Возврат, если длина массива равна 0.
- Поместите элемент в массив результатов, если элемент нечетный.
- Вызовите helperRecursiveFn с нарезанным первым элементом массива . Каждый раз будет отрезаться первый элемент массива, потому что мы уже проверили его на нечетность или четность.
Например: первый раз helperRecursiveFn будет вызываться с [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]. В следующий раз он будет вызываться с [2, 3, 4, 5, 6, 7, 8, 9, 10]и так далее, пока длина массива не станет равной 0.
Алгоритм линейного поиска
Алгоритм линейного поиска довольно прост. Скажем, вам нужно найти, существует ли число в данном массиве или нет.
Вы будете запускать простой цикл for и проверять каждый элемент, пока не найдете тот, который ищете.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
const array = [3, 8, 12, 6, 10, 2]; // Find 10 in the given array. function checkForN(arr, n) { for(let i = 0; i < array.length; i++) { if (n === array[i]) { return `${true} ${n} exists at index ${i}`; } } return `${false} ${n} does not exist in the given array.`; } checkForN(array, 10); |
Это алгоритм линейного поиска. Вы ищете каждый элемент в массиве один за другим линейным способом.
Временная сложность алгоритма линейного поиска
Есть только один цикл for, который будет выполняться n раз. Где n (в худшем случае) — длина данного массива. Здесь количество итераций (в худшем случае) прямо пропорционально входу (массиву длины).
Следовательно, временная сложность алгоритма линейного поиска равна линейной временной сложности: O(n) .
Алгоритм бинарного поиска
В линейном поиске вы можете исключить один элемент за раз. Но с помощью алгоритма бинарного поиска вы можете исключить сразу несколько элементов. Вот почему бинарный поиск быстрее, чем линейный поиск.
Здесь следует отметить, что бинарный поиск работает только с отсортированным массивом .
Этот алгоритм следует подходу «разделяй и властвуй». Найдем индекс числа 8 в [2, 3, 6, 8, 10, 12].
Шаг 1:
Найдите средний индекс массива.
|
1 2 3 4 5 6 7 |
const array = [2, 3, 6, 8, 10, 12]; let firstIndex = 0; let lastIndex = array.length - 1; let middleIndex = Math.floor((firstIndex + lastIndex) / 2); // middleIndex -> 2 |
Шаг 2:
Проверьте, находится ли элемент middleIndex > 8. Если да, это означает, что 8 находится слева от middleIndex. Следовательно, измените lastIndex на (middleIndex – 1).
Шаг 3:
Иначе, если элемент middleIndex < 8. Это означает, что 8 находится справа от middleIndex. Следовательно, измените firstIndex на (middleIndex + 1);
|
1 2 3 4 5 6 7 8 |
if (array[middleIndex] > 8) { lastIndex = middleIndex - 1; } else { firstIndex = middleIndex + 1; } |
Шаг 4:
С каждой итерацией middleIndex снова устанавливается в соответствии с новым firstIndex или lastIndex.
Давайте посмотрим все эти шаги вместе в формате кода.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
function binarySearch(array, element) { let firstIndex = 0; let lastIndex = array.length - 1; let middleIndex = Math.floor((firstIndex + lastIndex) / 2); while (array[middleIndex] !== element && firstIndex <= lastIndex) { if(array[middleIndex] > element) { lastIndex = middleIndex - 1; }else { firstIndex = middleIndex + 1; } middleIndex = Math.floor((firstIndex + lastIndex) / 2); } return array[middleIndex] === element ? middleIndex : -1; } const array = [2, 3, 6, 8, 10, 12]; binarySearch(array, 8); // OutPut -> 3 |
Вот визуальное представление приведенного выше кода.
|
1 2 3 4 |
firstIndex = middleIndex + 1; |
|
1 2 3 4 |
lastIndex = middleIndex - 1; |
|
1 2 3 4 |
array[middleIndex] === 8 // Found It |
Временная сложность бинарного поиска
Есть только один цикл while, который будет выполняться n раз. Но здесь количество итераций не зависит от ввода (длины массива).
Следовательно, временная сложность алгоритма бинарного поиска равна логарифмической временной сложности: O(log n) . И вы можете проверить граф O-обозначения. O (log n) быстрее, чем O (n).
Наивный алгоритм поиска
Наивный алгоритм поиска используется для определения того, содержит ли строка заданную подстроку. Например, проверьте, содержит ли «helloworld» подстроку «owo».
- Первый цикл основной строки (“helloworld”).
- Запустите вложенный цикл для подстроки (“owo”).
- Если символ не совпадает, то прерываем внутренний цикл, иначе продолжаем цикл.
- Если внутренний цикл завершен и получено совпадение, верните true, иначе продолжите внешний цикл.
Вот визуальное представление.
Вот реализация в коде.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
function naiveSearch(mainStr, subStr) { if (subStr.length > mainStr.length) return false; for(let i = 0; i < mainStr.length; i++) { for(let j = 0; j < subStr.length; j++) { if(mainStr[i + j] !== subStr[j]) break; if(j === subStr.length - 1) return true; } } return false; } |
Теперь давайте попробуем понять код выше.
- В строке 2 вернуть false, если длина подстроки больше длины основной строки.
- В строке 4 начните зацикливаться на mainString.
- В строке 5 запустите вложенный цикл в subString.
- В строке 6 прерываем внутренний цикл, если совпадений не найдено, и переходим к следующей итерации для внешнего цикла.
- В строке 7 вернуть true на последней итерации внутреннего цикла.
Временная сложность наивного поиска
Цикл внутри цикла (вложенный цикл). Оба цикла выполняются n раз. Следовательно, временная сложность алгоритма наивного поиска равна (n * n) квадратичной временной сложности: O(n^2) .
И, как обсуждалось выше, по возможности следует избегать любой временной сложности выше O(n). В следующем алгоритме мы увидим лучший подход с меньшей временной сложностью.
Алгоритм КМП
Алгоритм KMP — это алгоритм распознавания образов, и его немного сложно понять. Хорошо, попробуем найти, содержит ли строка «abcabcabspl» подстроку «abcabs».
Если мы попытаемся решить эту проблему с помощью алгоритма наивного поиска , он будет соответствовать первым 5 символам, но не 6-му символу. И нам придется начинать заново со следующей итерацией, мы потеряем весь прогресс в предыдущей итерации.
Итак, чтобы сохранить наш прогресс и использовать его, мы должны использовать нечто, называемое таблицей LPS. Теперь в нашей совпадающей строке «abcab» мы найдем самый длинный одинаковый префикс и суффикс.
Здесь в нашей строке «abcab» «ab» — самый длинный одинаковый префикс и суффикс.
Теперь мы начнем следующую итерацию поиска с индекса 5 (для основной строки). Мы сохранили двух персонажей из нашей предыдущей итерации.
Чтобы выяснить префикс, суффикс и с чего начать следующую итерацию, мы используем таблицу LPS.
LPS для нашей подстроки (“abcabs”) равен “0 0 0 1 2 0”.
Вот как рассчитать таблицу LPS.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
function calculateLpsTable(subStr) { let i = 1; let j = 0; let lps = new Array(subStr.length).fill(0); while(i < subStr.length) { if(subStr[i] === subStr[j]) { lps[i] = j + 1; i += 1; j += 1; } else { if(j !== 0) { j = lps[j - 1]; } else { i += 1; } } } return lps; } |
Вот реализация в коде с использованием таблицы LPS.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
function searchSubString(string, subString) { let strLength = string.length; let subStrLength = subString.length; const lps = calculateLpsTable(subString); let i = 0; let j = 0; while(i < strLength) { if (string[i] === subString[j]) { i += 1; j += 1; } else { if (j !== 0) { j = lps[j - 1]; } else { i += 1; } } if (j === subStrLength) return true; } return false; } |
Временная сложность алгоритма KMP
Есть только один цикл, который выполняется n раз. Следовательно, временная сложность алгоритма KMP равна линейной временной сложности: O(n) .
Обратите внимание, как улучшилась временная сложность по сравнению с простым алгоритмом поиска.
Алгоритм пузырьковой сортировки
Сортировка означает перестановку данных в порядке возрастания или убывания. Пузырьковая сортировка — один из многих алгоритмов сортировки.
В алгоритме пузырьковой сортировки мы меняем большее число на конец, сравнивая каждое число с предыдущим числом. Вот визуальное представление.
Реализация кода пузырьковой сортировки.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
function bubbleSort(array) { let isSwapped; for(let i = array.length; i > 0; i--) { isSwapped = false; for(let j = 0; j < i - 1; j++) { if(array[j] > array[j + 1]) { [array[j], array[j+1]] = [array[j+1], array[j]]; isSwapped = true; } } if(!isSwapped) { break; } } return array; } |
Попробуем разобраться в приведенном выше коде.
- Цикл от конца массива с переменной i к началу.
- Начните внутренний цикл с переменной j до (i – 1).
- Если массив [j] > массив [j + 1], поменяйте их местами.
- вернуть отсортированный массив.
Временная сложность алгоритма пузырьковой сортировки
Существует вложенный цикл, и оба цикла выполняются n раз, поэтому временная сложность для этого алгоритма равна (n * n), то есть квадратичной временной сложности O(n^2) .
Алгоритм сортировки слиянием
Алгоритм сортировки слиянием следует подходу «разделяй и властвуй». Это комбинация двух вещей – слияние и сортировка.
В этом алгоритме сначала мы делим основной массив на несколько отдельных отсортированных массивов.
Затем мы объединяем отдельные отсортированные элементы вместе в окончательный массив.
Давайте посмотрим на реализацию в коде.
Объединить отсортированный массив
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
function mergeSortedArray(array1, array2) { let result = []; let i = 0; let j = 0; while(i < array1.length && j < array2.length) { if(array1[i] < array2[j]) { result.push(array1[i]); i++; } else { result.push(array2[j]); j++; } } while (i < array1.length) { result.push(array1[i]); i++; } while (j < array2.length) { result.push(array2[j]); j++; } return result; } |
Приведенный выше код объединяет два отсортированных массива в новый отсортированный массив.
Алгоритм сортировки слиянием
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function mergeSortedAlgo(array) { if(array.length <= 1) return array; let midPoint = Math.floor(array.length / 2); let leftArray = mergeSortedAlgo(array.slice(0, midPoint)); let rightArray = mergeSortedAlgo(array.slice(midPoint)); return mergeSortedArray(leftArray, rightArray); } |
В приведенном выше алгоритме используется рекурсия для разделения массива на несколько массивов с одним элементом.
Временная сложность алгоритма сортировки слиянием
Попробуем рассчитать временную сложность алгоритма сортировки слиянием. Итак, взяв наш предыдущий пример ([6, 3, 5, 2]), потребовалось 2 шага, чтобы разделить его на несколько одноэлементных массивов.
**It took 2 steps to divide an array of length 4 - (2^2)
**.
Теперь, если мы удвоим длину массива (8), для деления потребуется 3 шага – (2 ^ 3). Означает, что удвоение длины массива не удваивает шаги.
Следовательно, временная сложность алгоритма сортировки слиянием равна логарифмической временной сложности O(log n) .
Алгоритм быстрой сортировки
Быстрая сортировка — один из самых быстрых алгоритмов сортировки. При быстрой сортировке мы выбираем один элемент, известный как точка опоры, и перемещаем все элементы (меньше точки опоры) влево от точки опоры.
Визуальное представление.
Мы будем повторять этот процесс для массива слева и справа от точки поворота, пока массив не будет отсортирован.
Реализация кода
Сводная утилита
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function pivotUtility(array, start=0, end=array.length - 1) { let pivotIndex = start; let pivot = array[start]; for(let i = start + 1; i < array.length; i++) { if(pivot > array[i]) { pivotIndex++; [array[pivotIndex], array[i]] = [array[i], array[pivotIndex]]; } } [array[pivotIndex], array[start]] = [array[start], array[pivotIndex]]; return pivotIndex; } |
Вышеприведенный код идентифицирует правильное положение поворота и возвращает индекс этого положения.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function quickSort(array, left=0, right=array.length-1) { if (left < right) { let pivotIndex = pivotUtility(array, left, right); quickSort(array, left, pivotIndex - 1); quickSort(array, pivotIndex + 1, right); } return array; } |
В приведенном выше коде используется рекурсия, чтобы перемещать опорную точку в правильное положение для левого и правого массива опорных точек.
Временная сложность алгоритма быстрой сортировки
НАИЛУЧШИЙ СЛУЧАЙ: Логарифмическая временная сложность — O(n log n)
СРЕДНИЙ СЛУЧАЙ: Логарифмическая временная сложность — O(n log n)
ХУДШИЙ СЛУЧАЙ: O(n^2)
Алгоритм сортировки по основанию
Сортировка по основанию также известна как алгоритм сортировки ведра.
Здесь сначала мы строим 10 сегментов индекса от 0 до 9. Затем мы берем последний символ в каждом числе и помещаем число в соответствующий сегмент. Получите новый порядок и повторите для предпоследнего символа каждого числа.
Продолжайте повторять описанный выше процесс, пока массив не будет отсортирован.
Реализация в коде.
// Подсчет цифр: приведенный ниже код подсчитывает количество цифр в данном элементе.
|
1 2 3 4 5 6 7 8 |
function countDigits(number) { if(number === 0) return 1; return Math.floor(Math.log10(Math.abs(number))) + 1; } |
// Получить цифру: приведенный ниже код дает цифру с индексом i справа.
|
1 2 3 4 5 6 7 8 9 |
function getDigit(number, index) { const stringNumber = Math.abs(number).toString(); const currentIndex = stringNumber.length - 1 - index; return stringNumber[currentIndex] ? parseInt(stringNumber[currentIndex]) : 0; } |
// MaxDigit: приведенный ниже фрагмент кода находит число с максимальным количеством цифр.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
<br>function maxDigit(array) { let maxNumber = 0; for(let i = 0; i < array.length; i++) { maxNumber = Math.max(maxNumber, countDigits(array[i])); } return maxNumber; } |
// Алгоритм Radix: использует все приведенные выше фрагменты для сортировки массива.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
function radixSort(array) { let maxDigitCount = maxDigits(array); for(let i = 0; i < maxDigitCount; i++) { let digitBucket = Array.from({length: 10}, () => []); for(let j = 0; j < array.length; j++) { let lastDigit = getDigit(array[j], i); digitBucket[lastDigit].push(array[j]); } array = [].concat(...digitBucket); } return array; } |
Временная сложность алгоритма сортировки по основанию
Существует вложенный цикл for, и мы знаем, что временная сложность вложенного цикла for составляет O(n^2). Но в этом случае оба цикла for не выполняются n раз.
Внешний цикл выполняется k (maxDigitCount) раз, а внутренний цикл выполняется m (длина массива) раз. Следовательно, временная сложность Radix Sort равна O (kxm) – (где kxm = n) Линейная временная сложность O (n)
Это нормально, если некоторые алгоритмы не срабатывали мгновенно, пройдитесь по ним несколько рази все получится!
Источник статьи: http://dev.to/
