Објашњени алгоритми грубе силе

Алгоритми грубе силе управо су оно што звуче - директне методе решавања проблема које се ослањају на пуку рачунарску снагу и испробавање сваке могућности уместо напредних техника за побољшање ефикасности.

На пример, замислите да имате мали локот са 4 цифре, свака од 0-9. Заборавили сте своју комбинацију, али не желите да купите још један катанац. Пошто се не можете сетити ниједне цифре, морате отворити браву методом грубе силе.

Дакле, вратите све бројеве на 0 и покушајте их један по један: 0001, 0002, 0003 и тако даље док се не отворе. У најгорем случају, било би потребно 104 или 10 000 покушаја да пронађете вашу комбинацију.

Класичан пример у рачунарству је проблем трговца путника (ТСП). Претпоставимо да продавац треба да посети 10 градова широм земље. Како одредити редослед по коме треба посетити те градове тако да се умањи укупан пређени пут?

Решење грубе силе је једноставно израчунати укупну удаљеност за сваку могућу руту, а затим одабрати најкраћу. Ово није нарочито ефикасно јер је могуће паметне алгоритме елиминисати многе могуће руте.

Временска сложеност грубе силе је О (м н ) , што се понекад записује као О (н * м). Дакле, ако бисмо претраживали низ знакова „н“ у низу знакова „м“ користећи грубу силу, требало би нам н * м покушаја.

Више информација о алгоритмима

У рачунарским наукама, алгоритам је једноставно скуп поступака за решавање датог проблема. Алгоритми могу бити дизајнирани за извршавање прорачуна, обраду података или извршавање задатака аутоматизованог закључивања.

Ево како их дефинише Википедиа:

Алгоритам је ефикасна метода која се може изразити у ограниченој количини простора и времена и на добро дефинисаном формалном језику за израчунавање функције. Полазећи од почетног стања и почетног уноса (можда празног), упутства описују прорачун који се, када се изврши, одвија кроз коначан број добро дефинисаних узастопних стања, на крају производећи „излаз“ и завршавајући се у коначном завршном стању. Прелазак из једног стања у друго није нужно детерминистички; неки алгоритми, познати као случајни алгоритми, укључују случајни унос.

Постоје одређени захтеви којих се алгоритам мора придржавати:

  1. Дефинитивност: Сваки корак у процесу је прецизно наведен.
  2. Ефикасна израчунавост: Сваки корак у процесу може извршити рачунар.
  3. Коначност: Програм ће се на крају успешно завршити.

Неке уобичајене врсте алгоритама укључују:

  • алгоритми за сортирање
  • алгоритми претраживања
  • алгоритми компресије.

Класе алгоритама укључују

  • Графикон
  • Динамичко програмирање
  • Сортирање
  • У потрази
  • Жице
  • Математика
  • Рачунарска геометрија
  • Оптимизација
  • Остало.

Иако технички нису класа алгоритама, структуре података се често групишу са њима.

Ефикасност

Алгоритми се најчешће процењују према њиховој ефикасности и количини рачунарских ресурса потребних за извршавање задатка.

Уобичајени начин процене алгоритма је сагледавање његове временске сложености. То показује како време рада алгоритма расте како величина улаза расте. Будући да алгоритми данас морају да раде на великим улазима података, за наше алгоритме је неопходно да имају релативно брзо време рада.

Алгоритми сортирања

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

Куицксорт

Не постоји дискусија о сортирању која се може завршити без брзог сортирања. Ево основног концепта: Брзо сортирање

Сортирање спајањем

Алгоритам сортирања који се ослања на концепт како се сортирани низови спајају да би се добили један сортирани низови. Прочитајте више о томе овде: Мергесорт

Наставни план и програм фрееЦодеЦампа снажно наглашава стварање алгоритама. То је зато што су алгоритми учења добар начин за увежбавање вештина програмирања. Анкетари најчешће тестирају кандидате на алгоритмима током разговора за посао програмера.

Књиге о алгоритмима у ЈаваСцрипт-у:

Структуре података у ЈаваСцрипт-у

  • Бесплатна књига која покрива структуре података у ЈаваСцрипт-у
  • ГитБоок

Учење ЈаваСцрипт структура података и алгоритама - друго издање

  • Обухвата објектно оријентисано програмирање, прототипско наслеђивање, алгоритме за сортирање и претраживање, брзо сортирање, спајање, бинарно стабло претраживања и напредне концепте алгоритама
  • Амазон
  • ИСБН-13: 978-1785285493

Структуре података и алгоритми са ЈаваСцрипт-ом: Доношење класичних рачунарских приступа на мрежу

  • Покрива алгоритме рекурзије, сортирања и претраживања, повезане листе и бинарна стабла претраживања.
  • Амазон
  • ИСБН-13: 978-1449364939