Майже завжди допоможуть вирішити проблему: 6 алгоритмів, які має знати кожен розробник

Розробник Річард Уерпам у своєму блозі на Medium зізнається, що він не великий шанувальник структур даних і алгоритмів. Але, попрацювавши над різними проєктами, виявив, що є шість важливих алгоритмів. Вони майже завжди можуть допомогти вирішити проблему. Про них він і розповідає у цій статті. Передаємо йому слово.

1Алгоритм сортування

Що таке сортування? Це алгоритм, який впорядковує елементи у списку.

Важливі алгоритми сортування:

• сортування бульбашкою: найпростіший алгоритм сортування, який працює шляхом порівняння суміжних елементів і заміни їх, якщо вони розміщені неправильно;
• сортування злиттям: техніка сортування, яка використовує стратегію «розділяй і володарюй»;
• швидке сортування: популярний алгоритм сортування, який виконує в середньому n log n порівнянь під час сортування масиву з n елементів. Це дуже ефективний і швидкий алгоритм;
• сортування купою: відбувається за допомогою візуалізації елементів масиву як особливого типу повного бінарного дерева (купи).

2Алгоритм пошуку

Що таке пошук? Це алгоритм, який знаходить елемент у наборі даних.

Важливі алгоритми пошуку:

• Двійковий пошук: використовує стратегію «розділяй і володарюй». Відсортований список ділиться на дві половини, а елемент порівнюється із середнім елементом списку.
• Пошук у ширину (BFS): це алгоритм обходу графу, який починає з кореневого вузла та досліджує всі сусідні вузли.
• Пошук у глибину (DFS): цей алгоритм починає з першого вузла графу та йде все глибше й глибше, доки ми не знайдемо цільовий вузол або вузол без нащадків.

3Динамічне програмування

Динамічне програмування (DP) — це алгоритмічна техніка для розв’язання проблеми оптимізації. Для цього її розбивають на простіші підпроблеми і вважають, що оптимальне рішення загальної проблеми залежить від оптимального рішення її підпроблем.

4Алгоритм рекурсії

Рекурсія — це техніка вирішення проблем, у якій рішення залежить від розв’язків менших випадків тієї самої проблеми. Обчислення факторіалів є класичним прикладом рекурсивного програмування.

У кожній рекурсивній програмі є базова послідовність кроків:

• Налаштуйте алгоритм. Рекурсивні програми часто вимагають вихідного значення. Для цього використовують параметр, переданий у функцію або нерекурсивну функцію шлюзу, яка встановлює початкові значення для рекурсивного обчислення.
• Перевірте, чи поточні значення, які обробляються, відповідають базовому випадку. Якщо так, обробіть значення та поверніть його.
• Перефразуйте рішення з точки зору меншої або простішої підпроблеми чи підпроблем.
• Застосуйте алгоритм до підзадачі.
• Щоб сформулювати відповідь, об’єднайте результати.
• Поверніть результати.

5Розділяй та володарюй

Алгоритм «Розділяй та володарюй» рекурсивно ділить проблему на дві або більше підпроблем одного або спорідненого типу, доки вони не стануть достатньо простими для вирішення.

Алгоритм «Розділяй та володарюй» вимагає таких кроків: 

• розділіть вихідну проблему на підпроблеми;
• вирішуйте кожну підпроблему по черзі, рекурсивно;
• об’єднайте рішення підпроблем, щоб отримати рішення всієї проблеми.

6Хешування

Хешування — це техніка або процес, який використовує хеш-функцію для відображення ключів та значень у хеш-таблиці. Це робиться для швидшого доступу до елементів. Ефективність відображення визначається ефективністю хеш-функції.

Висновок

Зараз існує дуже багато алгоритмів різної складності. Інколи важко визначити, які з них обов’язково треба знати розробнику. Часто це залежить від особистих уподобань і сфери роботи. Але в цій статті висвітлено ті алгоритми, які вам точно знадобляться. 

Автор: Річард Уерпам

Текст адаптувала Євгенія Козловська