Типи алгоритмів - Дізнайтеся про найкращі 6 найважливіших типів алгоритмів

Зміст:

Anonim

Вступ до алгоритмів

Алгоритм - це послідовність кроків, що описують, як можна вирішити проблему. Кожна комп'ютерна програма, яка закінчується результатом, в основному заснована на алгоритмі. Але алгоритми не обмежуються лише для використання в комп'ютерних програмах, вони також можуть бути використані для вирішення математичних задач та багатьох питань повсякденного життя. Виходячи з того, як вони функціонують, ми можемо розділити Алгоритми на кілька типів. Давайте розглянемо деякі важливі.

Типи алгоритму

Існує багато типів алгоритмів, але основними типами алгоритмів є:

1) Рекурсивний алгоритм

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

Такі проблеми, як Ханойська вежа або DFS графіка, можна легко вирішити за допомогою цих алгоритмів.

Наприклад, ось код, який знаходить факторіал за допомогою алгоритму рекурсії:

Факт (y)

Якщо y дорівнює 0

повернути 1

return (y * Факт (y-1)) / * тут відбувається рекурсія * /

2) Розділіть і підкоріть алгоритм

Це ще один ефективний спосіб вирішення багатьох проблем. У алгоритмах Divide and Conquer діліть алгоритм на дві частини, перша частина ділить проблему на менші підпрограми одного типу. Потім у другій частині ці менші проблеми вирішуються, а потім додаються разом (поєднуються) для отримання остаточного вирішення проблеми.

Об'єднання сортування та швидке сортування можна виконати за допомогою алгоритмів ділення та підкорення. Ось псевдокод алгоритму сортування злиття, щоб навести приклад:

MergeSorting (ar (), l, r)

Якщо r> l

  1. Знайдіть середину, щоб поділити даний масив на дві половини:

середина m = (l + r) / 2

  1. Виклик злиттяСортування за перше півріччя:

Виклик mergeSorting (ar, l, m)

  1. Виклик об'єднанняSorting для другої половини:

Виклик mergeSorting (ar, m + 1, r)

  1. Об’єднайте половинки, відсортовані на етапах 2 та 3:

Злиття виклику (ar, l, m, r)

3) Алгоритм динамічного програмування

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

Послідовність Фібоначчі є хорошим прикладом для алгоритмів динамічного програмування, ви можете бачити це, працюючи в псевдокоді:

Фібоначчі (N) = 0 (для n = 0)

= 0 (для n = 1)

= Фібоначчі (N-1) + Фіначчі (N-2) (для n> 1)

4) Жадібний алгоритм

Ці алгоритми використовуються для вирішення задач оптимізації. У цьому алгоритмі ми знаходимо оптимально локальне рішення (не враховуючи жодних наслідків у майбутньому) та сподіваємось знайти оптимальне рішення на глобальному рівні.

Метод не гарантує, що нам вдасться знайти оптимальне рішення.

Алгоритм містить 5 компонентів:

  • Перший - це набір кандидатів, з якого ми намагаємось знайти рішення.
  • Функція відбору, яка допомагає вибрати найкращого можливого кандидата.
  • Функція техніко-економічного обґрунтування, яка допомагає вирішити, чи можна кандидата використовувати для пошуку рішення.
  • Об'єктивна функція, яка присвоює значення можливому рішенню або частковому рішенню
  • Функція рішення, яка повідомляє, коли ми знайшли рішення проблеми.

Алгоритм Хаффмана та алгоритм Дейкстри - два найважливіші приклади, коли використовується алгоритм жадібності.

У кодуванні Хаффмана алгоритм проходить через повідомлення і залежно від частоти символів у цьому повідомленні для кожного символу він призначає кодування змінної довжини. Для кодування Хаффмана потрібно спочатку побудувати дерево Хаффмана з введених символів, а потім пройти через дерево, щоб призначити коди символам.

5) Алгоритм грубої сили

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

Ось приклад послідовного пошуку, здійсненого за допомогою грубої сили:

Алгоритм S_Search (A (0..n), X)

A (n) ← X

i ← 0

У той час як A (i) ≠ X так

i ← i + 1

якщо я <n повернути i

інше повернути -1

6) Алгоритм зворотного відстеження

Зворотний трек - це техніка пошуку рішення проблеми при поступовому підході. Він вирішує проблеми рекурсивно і намагається дійти до вирішення проблеми, вирішуючи по одній частині проблеми за один раз. Якщо одне з рішень виходить з ладу, ми видаляємо його і повертаємо назад, щоб знайти інше рішення.

Іншими словами, алгоритм зворотного відстеження вирішує підпроблему, і якщо не вдалося вирішити проблему, він скасовує останній крок і починає знову шукати рішення проблеми.

Проблема N Queens - хороший приклад, щоб побачити алгоритм зворотного відстеження в дії. Проблема "N Queen" зазначає, що в шаховій дошці є N кусочків королеви, і ми повинні їх розташувати так, щоб жодна королева не могла напасти на будь-яку іншу королеву в дошці, коли вона була організована.

Тепер давайте розглянемо алгоритм SolveNQ і перевіримо дійсні функції для вирішення проблеми:

CheckValid (Шахова дошка, рядок, стовпець)

Старт

Якщо зліва від поточного стовпця є королева, то поверніться помилково

Якщо королева знаходиться у верхній лівій діагоналі, поверніть помилкову

Якщо королева знаходиться в нижній лівій діагоналі, поверніться помилково

Повернення справжнє

Кінець

SolveNQ (Дошка, стовпець)

Старт

Якщо всі стовпці заповнені, то поверніть true

Для кожного ряду, присутнього на шаховій дошці

Зробіть

Якщо, CheckValid (дошка, х, стовпець), то

Встановіть королеву в клітинку (х, стовпець) на дошці

Якщо SolveNQ (дошка, стовпець + 1) = True, то поверніть true.

Інше, вийміть королеву з комірки (х, стовпчик) з дошки

Зроблено

Повернути помилково

Кінець

Висновок - Типи алгоритмів

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

Рекомендовані статті

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

  1. Вступ до алгоритму
  2. Алгоритм програмування
  3. Питання інтерв'ю з алгоритмом
  4. Факторський в Python | Техніки
  5. Швидке сортування алгоритмів на Java
  6. Топ-6 алгоритмів сортування в JavaScript