7 алгоритма, които всеки програмист трябва да знае

Като студент по програмиране вероятно сте научили много различни алгоритми по време на кариерата си. Владеенето на различни алгоритми е абсолютно необходимо за всеки програмист.

С толкова много алгоритми може да бъде предизвикателство да следите какво е от съществено значение. Ако се подготвяте за интервю или просто уточнявате уменията си, този списък ще го направи сравнително лесен. Прочетете, докато изброяваме най -важните алгоритми за програмистите.

1. Алгоритъмът на Дейкстра

Едсгер Дайкстра беше един от най -влиятелните компютърни учени на своето време и той допринесе за това много различни области на изчислителната наука, включително операционни системи, конструиране на компилатори и много други Повече ▼. Един от най -забележителните приноси на Дейкстра е изобретателността на неговия алгоритъм за най -кратък път за графики, известен също като Алгоритъм на най -краткия път на Дейкстра.

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

Алгоритъмът обикновено се прилага с помощта на набор. Алгоритъмът на Dijkstra е много ефективен, когато се прилага с минимална купчина; можете да намерите най -краткия път само за O (V+ElogV) време (V е броят на върховете и E е броят на ръбовете в дадена графика).

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

Въпросите за интервю обикновено включват алгоритъма на Джикстра, така че силно препоръчваме да разберете сложните му подробности и приложения.

2. Обединяване Сортиране

В този списък имаме няколко алгоритма за сортиране и сортирането на сливане е един от най -важните алгоритми. Това е ефективен алгоритъм за сортиране, базиран на програмната техника Divide and Conquer. В най-лошия сценарий, сортирането при сливане може да сортира числа „n“ само за O (nlogn) време. В сравнение с примитивните техники за сортиране като Сортиране на балончета (което отнема O (n^2) време), сортирането на сливане е отлично ефективно.

Свързани: Въведение в алгоритъма за сортиране на сливане

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

3. Бързо сортиране

Quicksort е друг алгоритъм за сортиране, базиран на техниката за програмиране Divide and Conquer. В този алгоритъм първо се избира елемент като опора, а след това целият масив се разделя на дялове около тази опора.

Както вероятно се досещате, доброто завъртане е от решаващо значение за ефективното сортиране. Пивотът може да бъде или случаен елемент, медиен елемент, първи елемент или дори последен елемент.

Реализациите на бързото сортиране често се различават по начина, по който избират пивот. В средния случай бързото сортиране ще сортира голям масив с добър пивот само за O (nlogn) време.

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

4. Дълбоко първо търсене

Depth First Search (DFS) е един от първите графични алгоритми, преподавани на учениците. DFS е ефективен алгоритъм, използван за преминаване или търсене на графика. Той може също да бъде модифициран, за да се използва при обхождане на дървета.

Обхождането на DFS може да започне от произволен възел и да се потопи във всеки съседен връх. Алгоритъмът се връща назад, когато няма непосетен връх или има задънена улица. DFS обикновено се реализира със стек и булев масив за проследяване на посетените възли. DFS е лесен за изпълнение и изключително ефективен; тя работи (V+E), където V е броят на върховете и E е броят на ръбовете.

Типичните приложения на DFS обхода включват топологично сортиране, откриване на цикли в графика, намиране на пътеки и намиране на силно свързани компоненти.

5. Търсене на първа ширина

Breadth-First Search (BFS) е известен също като обхождане на ниво за дървета. BFS работи в O (V+E) подобно на DFS алгоритъм. BFS обаче използва опашка вместо стека. DFS се гмурва в графиката, докато BFS пресича графиката по ширина.

BFS алгоритъмът използва опашка, за да следи върховете. Непосетените съседни върхове се посещават, маркират и поставят на опашка. Ако върхът няма съседни върхове, тогава върхът се премахва от опашката и се изследва.

BFS обикновено се използва в peer-to-peer мрежи, най-краткия път на непретеглена графика и за намиране на минималното обхващащо дърво.

6. Двоично търсене

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

Най-лошата времева сложност на двоичното търсене е O (logn), което го прави много ефективен при търсене на линейни масиви.

7. Минимални алгоритми на обхващащо дърво

Минималното обхващащо дърво (MST) на графика има минималните разходи сред всички възможни обхващащи дървета. Цената на дървото зависи от теглото на ръбовете му. Важно е да се отбележи, че може да има повече от едно минимално обхващащо дърво. Има два основни алгоритъма за MST, а именно Kruskal's и Prim's.

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

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

Алгоритъмът на Prim също използва алчно свойство и е идеален за плътни графики. Централната идея в MST на Prim е да има два различни набора от върхове; единият набор съдържа нарастващия MST, докато другият съдържа неизползвани върхове. На всяка итерация се избира минималната граница на теглото, която ще свързва двата набора.

Алгоритмите за минимално обхващащо дърво са от съществено значение за клъстерния анализ, таксономията и излъчващите мрежи.

Ефективният програмист владее алгоритми

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

Въведение в алгоритъма за сортиране на Shell

Докато сортирането на черупки не е най -ефективният метод, начинаещите имат много да спечелят от практикуването му.

Прочетете Напред

За автора