Обяснени алгоритми за груба сила

Алгоритмите Brute Force са точно това, което звучат - ясни методи за решаване на проблем, които разчитат на чиста изчислителна мощ и изпробване на всяка възможност, а не на усъвършенствани техники за подобряване на ефективността.

Например, представете си, че имате малък катинар с 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. Крайност: Програмата в крайна сметка ще бъде успешно прекратена.

Някои често срещани типове алгоритми включват:

  • алгоритми за сортиране
  • алгоритми за търсене
  • алгоритми за компресиране.

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

  • Графика
  • Динамично програмиране
  • Сортиране
  • Търсене
  • Струни
  • Математика
  • Изчислителна геометрия
  • Оптимизация
  • Разни.

Въпреки че технически не са клас алгоритми, Структурите на данни често се групират с тях.

Ефективност

Алгоритмите най-често се оценяват по тяхната ефективност и количеството изчислителни ресурси, които са им необходими, за да изпълнят задачата си.

Чест начин за оценка на алгоритъма е да се разгледа неговата сложност във времето. Това показва как времето за работа на алгоритъма нараства с увеличаването на размера на входа. Тъй като днешните алгоритми трябва да работят на големи входове от данни, за нашите алгоритми е от съществено значение да имат достатъчно бързо време за работа.

Алгоритми за сортиране

Алгоритмите за сортиране се предлагат в различни вкусове в зависимост от вашата необходимост. Някои, много разпространени и широко използвани са:

Quicksort

Няма дискусия за сортиране, която да завърши без бързо сортиране. Ето основната концепция: Бързо сортиране

Mergesort

Алгоритъм за сортиране, който разчита на концепцията как да се сортират масиви се обединяват, за да се даде един сортиран масив. Прочетете повече за това тук: Mergesort

Учебната програма на freeCodeCamp подчертава силно създаването на алгоритми. Това е така, защото ученето на алгоритми е добър начин за упражняване на умения за програмиране. Интервюиращите най-често тестват кандидатите по алгоритми по време на интервюта за работа на разработчици.

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

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

  • Безплатна книга, която обхваща структурите на данни в JavaScript
  • GitBook

Изучаване на структури от данни и алгоритми на JavaScript - второ издание

  • Обхваща обектно-ориентирано програмиране, прототипно наследяване, алгоритми за сортиране и търсене, бързо сортиране, обединяване, бинарни дървета за търсене и разширени концепции на алгоритъма
  • Amazon
  • ISBN-13: 978-1785285493

Структури на данни и алгоритми с JavaScript: Представяне на класически изчислителни подходи в мрежата

  • Обхваща алгоритми за рекурсия, сортиране и търсене, свързани списъци и бинарни дървета за търсене.
  • Amazon
  • ISBN-13: 978-1449364939