Пояснення алгоритмів грубої сили

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

Наприклад, уявіть, що у вас є маленький замок із 4 цифрами, кожна від 0 до 9. Ви забули свою комбінацію, але не хочете купувати черговий замок. Оскільки ви не можете запам'ятати жодної цифри, вам доведеться застосувати метод грубої сили, щоб відкрити замок.

Отже, ви встановлюєте всі числа назад на 0 і пробуєте їх одне за одним: 0001, 0002, 0003 і так далі, поки воно не відкриється. У гіршому варіанті знадобиться 104 або 10 000 спроб знайти вашу комбінацію.

Класичним прикладом інформатики є проблема продавця-подорожуючого (TSP). Припустимо, продавцю потрібно відвідати 10 міст по всій країні. Як визначити порядок відвідування цих міст таким чином, щоб загальна пройдена відстань була зведена до мінімуму?

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

Часова складність грубої сили становить O (m n ) , що іноді записують як O (n * m). Отже, якби ми шукали рядок символів "n" у рядку символів "m", використовуючи грубу силу, це зайняло б нам n * m спроб.

Більше інформації про алгоритми

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

Ось як їх визначає Вікіпедія:

Алгоритм - це ефективний метод, який можна виразити в кінцевій кількості простору та часу та чітко визначеною формальною мовою для обчислення функції. Починаючи з початкового стану та початкового введення (можливо, порожнього), інструкції описують обчислення, які, виконуючись, проходять через кінцеву кількість чітко визначених послідовних станів, зрештою виробляючи "вихід" і закінчуючи кінцевим кінцевим станом. Перехід з одного стану в наступний не обов'язково детермінований; деякі алгоритми, відомі як рандомізовані алгоритми, включають випадкові дані.

Існують певні вимоги, яких повинен дотримуватися алгоритм:

  1. Визначеність: Кожен етап у процесі точно зазначений.
  2. Ефективна обчислюваність: кожен крок у процесі може здійснюватися комп’ютером.
  3. Кінцевість: програма врешті-решт успішно завершиться.

Деякі загальні типи алгоритмів включають:

  • алгоритми сортування
  • алгоритми пошуку
  • алгоритми стиснення.

Класи алгоритмів включають

  • Графік
  • Динамічне програмування
  • Сортування
  • Пошук
  • Струни
  • Математика
  • Обчислювальна геометрія
  • Оптимізація
  • Різне.

Хоча технічно це не клас алгоритмів, Структури даних часто групуються з ними.

Ефективність

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

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

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

Алгоритми сортування бувають різних видів, залежно від вашої потреби. Деякі, дуже поширені та широко використовувані:

Швидкий сорт

Не існує дискусії щодо сортування, яка могла б закінчитися без швидкого сортування. Ось основна концепція: Швидке сортування

Злиття

Алгоритм сортування, який спирається на концепцію, як відсортовані масиви об'єднуються, щоб отримати один відсортований масив. Детальніше про це читайте тут: Mergesort

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

Книги про алгоритми в JavaScript:

Структури даних у JavaScript

  • Безкоштовна книга, яка висвітлює структури даних у JavaScript
  • GitBook

Вивчення структур даних та алгоритмів JavaScript - друге видання

  • Охоплює об’єктно-орієнтоване програмування, прототипне успадкування, алгоритми сортування та пошуку, швидке сортування, злиття, сортування двійкових дерев пошуку та розширені концепції алгоритмів
  • Амазонка
  • ISBN-13: 978-1785285493

Структури даних та алгоритми з JavaScript: Застосування класичних обчислювальних підходів до Інтернету

  • Охоплює алгоритми рекурсії, сортування та пошуку, зв’язані списки та двійкові дерева пошуку.
  • Амазонка
  • ISBN-13: 978-1449364939