Структуре података и алгоритми: комплетан водич за програмере

Информатек Дигитал » Средства » Структуре података и алгоритми: комплетан водич за програмере

Алгоритми и структуре података су два дела која се уклапају попут слагалице: један дефинише поступак за решавање проблема, а други одређује где и како чувамо информације. Иако може звучати академски, савладавање овог пара је оно што разликује код који само ради од кода који лети и скалира се без кварова.

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

Шта су структуре података и алгоритми?

Структура података је, у суштини, специфичан начин организовања и складиштења информација у меморији како би се омогућила ефикасна манипулација. Ова организација није случајна: она директно одређује које су операције брзе, а које постају скупе (уметање, претраживање, брисање, прелазак итд.).

Када одаберете праву структуру података, ваш програм може да обрађује велике количине података без икаквог напора; када одаберете лоше, чак и мала апликација може постати спора, трошити превише меморије или постати немогућа за одржавање током времена.

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

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

Са теоријске перспективе, аутори попут Никлауса Вирта популаризовали су идеју да алгоритми + структуре података = програми још 70-их . Деценијама касније, ово остаје подједнако тачно: без обзира да ли програмирате у Јави, Пајтону, C++ или долазите са обуке за почетнике, оно што ће бити потребно на интервјуима и озбиљним пројектима је способност да ефикасно изаберете и комбинујете оба елемента.

Зашто су толико важни у програмирању?

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

Структуре података се користе за чување информација на организован и кохерентан начин, у зависности од проблема. Није исто увек приступати првом елементу, претраживати по кључу, понављати редослед, уметати у средину или често брисати; сваки образац коришћења је боље прилагођен другој структури.

Алгоритми, са своје стране, нам омогућавају да ефикасно обрађујемо ове податке : сортирање, филтрирање, претраживање елемената, проналажење оптималних путања, откривање образаца путем анализе података , оптимизација ресурса и тако даље. Многи проблеми који делују тешки постају тривијални када пронађете праву комбинацију алгоритма и структуре података.

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

Штавише, формална и професионална обука се често врти око ове области. Многи универзитети и програми високог образовања укључују предмет под називом Структуре података и алгоритми , са званичним наставним планом и програмом, предусловима, предавањима и практичним вежбама, испитима и задацима, јер се сматра основним предметом за сваког софтверског инжењера.

Предуслови и неопходне основе

Да бисте извукли максимум из проучавања структура података и алгоритама, корисно је да будете упознати са неким програмским језиком опште намене, као што су Јава, Пајтон или C++ . Не морате бити стручњак, али требало би да будете упознати са основним концептима као што су променљиве, типови података, условни изрази, петље, функције и прослеђивање параметара.

Такође је невероватно корисно разумети концепт алгоритамске сложености и нотацију „Big O“: како се време извршавања или коришћење меморије повећавају са повећањем величине података (n). Познавање разликовања између O(1), O(log n), O(n), O(n log n) и O(n²) омогућава вам да објективно упоредите алтернативе и образложите своје одлуке.

Још један важан аспект је имати неко искуство у решавању проблема : вежбе структурираног програмирања, мали логички изазови, једноставне ката вежбе итд. Што више тренирате свој „нос“ да разложите проблем на кораке, лакше ћете видети која структура података одговара сваком случају.

Неки наставни планови експлицитно наводе предуслове или кореквизите за курс Структуре података и алгоритми, као што су положени Основи програмирања, Програмирање I или Дискретна математика. Ово је логично: без чврсте основе у основном програмирању и мало логике, лако је постати фрустриран овим предметом.

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

Најчешће коришћене структуре података

У рачунарству постоји много структура података , али постоји група „основних“ које се понављају изнова и изнова: низови (вектори), стекови, редови, повезане листе, стабла, графови, покушаји-суме и хеш табеле. Разумевање како функционишу, које операције нуде и њихових типичних трошкова је кључно за вешто програмирање.

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

Низови

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

Замислите низ величине 4 који садржи вредности 1, 2, 3 и 4. Свака позиција има индекс (0, 1, 2, 3) и можете директно приступити било ком елементу са његовим индексом у константном времену O(1). Ово чини низове веома ефикасним за насумично читање.

Постоје две главне категорије: једнодимензионални низови (један ред елемената) и вишедимензионални низови (на пример, матрице, које су низови низова). Многи програмски језици нуде обе варијанте изворно или са малим разликама у синтакси и перформансама.

Основне операције на низу су обично:

• Уметни: постављање елемента на одређену позицију, што у статичким низовима може укључивати померање других елемената.
• Добиј: приступање елементу на датом индексу, обично O(1).
• Обриши: обрише или означи као празан елемент на одређеној позицији, обично померањем елемената улево.
• Величина: проверите колико је елемената сачувано или максимални капацитет низа.

На интервјуима и испитима, вежбе попут проналажења друге минималне вредности у низу , проналажења првог јединственог целог броја, спајања два сортирана низа или преуређивања позитивних и негативних бројева уз задржавање одређених својстава су веома честе. Све се то ослања на приступ индексу и линеарне или двоструке обиласке.

Стекови

Стек је линеарна структура података која прати LIFO принцип: Последњи ушао, први изашао. Замислите гомилу књига постављених једна на другу: можете узимати или остављати књиге само са врха.

Ово понашање значи да можемо приступити само елементу на врху стека . Не можемо уклонити средњи елемент без претходног уклањања елемената изнад њега. Ово га чини идеалном структуром за моделирање историје акција (поништи), угнежђених позива функција, навигације (назад/напред) и тако даље.

Типичне операције са стеком су:

• гурање: уметните нову ставку на врх.
• Поп: издвојити и вратити елемент на врху, смањујући величину стека.
• Врх или завири: консултујте горњи елемент без његовог брисања.
• ПразноПроверите да ли је батерија празна.

У контексту интервјуа, виде се проблеми као што су извршавање израза у постфиксној нотацији (RPN), уређивање елемената коришћењем само стекова или провера да ли је низ заграда (и других симбола) правилно балансиран коришћењем push и pop.

У пракси, многе интерне имплементације језика (на пример, стек системских позива ) раде по истим принципима, чак и ако их не видимо директно.

Редови

Ред је још једна линеарна структура података, али уместо да прати LIFO принцип, користи FIFO модел: Први уђе, први изађе. Најјаснија аналогија је ред људи који чекају на благајни у биоскопу.

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

Основне операције реда чекања укључују:

• У реду: уметните нову ставку на крај реда.
• Декуеуе: уклонити и вратити елемент који се налази на почетку.
• Предњи или горњи деоконсултујте прву ставку без њеног уклањања.
• Празно: провери да ли је ред празан.

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

Поред основног реда, постоје варијанте као што су кружни ред , ред са приоритетом или двоструки редови (deque), које нуде додатне операције и побољшавају перформансе у одређеним сценаријима.

повезане листе

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

Сваки чвор обично садржи два дела: податке који се чувају и показивач (или више њих) који указује на следећи чвор у низу (и, у случају двоструко повезаних листа, и на претходни). Листа се управља преко референце на њен почетак, који указује на први чвор, а у сложенијим листама, одржава се и референца на реп.

Постоје две главне варијанте:

• једноструко повезана листа: сваки чвор указује само на следећи; путања је обично у једном смеру.
• двоструко повезана листаСваки чвор указује на следећи и претходни чвор, олакшавајући двосмерне преласке и ефикасније операције брисања.

Типичне операције на повезаним листама укључују:

• Убаци на почетак: уметните нови чвор на почетак листе.
• Убаци на крају: додаје чвор на крај, ажурирајући ред ако постоји.
• Избрисати: уклонити одређени чвор, подешавајући показиваче суседних чворова.
• Обриши на почетку: обришите први чвор и померите главу на следећи.
• Претрага: пређите кроз листу тражећи одређену вредност.
• ПразноПровери да ли је заглавље null и да ли листа нема елементе.

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

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

Арболес

Стабло је хијерархијска структура података састављена од чворова повезаних ивицама. За разлику од општих графова, стабло нема циклусе: увек постоји корен, деца, родитељи, браћа и сестре, листови, нивои и подстабла, са организацијом типа „породица“ или „организациона шема“.

Стабла су веома корисна када желимо да представимо хијерархијске односе или да поделимо проблем на мање подпроблеме: системе датотека, меније, DOM структуре у прегледачима, стабла одлучивања у вештачкој интелигенцији итд.

Постоји много врста дрвећа, укључујући:

• N-арно дрво: сваки чвор може имати променљив (и могуће велики) број деце.
• Уравнотежено дрво: одржава своје гране на сличној дубини како би се избегло смањење перформанси.
• Бинарно дрво: сваки чвор има највише два детета (лево и десно).
• Бинарно стабло претраживања (BST)бинарно дрво са својством да је све лево од чвора мање, а све десно веће (према неком критеријуму уређења).
• AVL дрво, црвено-црно, 2-3 и друге варијантеОво су балансирана стабла претраживања која гарантују добра ограничења сложености у операцијама уметања, брисања и претраживања.

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

Штавише, алгоритми обиласка (преордер, инордер, постордер, ниво по ниво) су фундаментални за многе наредне процесе: сортирано штампање, процену израза, серијализацију и десеријализацију стабла итд.

графова

Граф генерализује концепт стабла тако што дозвољава циклусе и вишеструке произвољне везе између чворова. Састоји се од скупа врхова (чворова) и скупа ивица које повезују парове врхова, понекад са придруженом тежином или ценом.

Постоји неколико врста графова: неусмерени (границе немају правац, однос је двосмеран) и усмерени (границе имају почетак и одредиште). Такође се могу класификовати као пондерисани или непондерисани, повезани или неповезани, са или без циклуса итд.

У коду, графови се обично представљају на два основна начина:

• Матрица суседности: матрица где ћелија означава да ли постоји ивица између чворова i и j (и могуће тежину везе).
• Листа суседности: за сваки чвор се чува листа његових суседа, што штеди меморију у ретким графовима.

Најкласичнији алгоритми за обилазак су претрага у ширину (BFS) и претрага у дубину (DFS) . Оба се користе као градивни блокови за мноштво проблема: провера да ли је граф повезан, откривање циклуса, проналажење повезаних компоненти итд.

У техничким тестовима, уобичајено је да се тражи да се имплементира BFS и DFS, провери да ли граф формира дрво, преброји број грана или потраже краће путање између два чвора (на пример, на мапи градова) користећи варијанте као што су Дајкстра или BFS у нетежинским графовима.

Покушаји или префиксна стабла

Префиксно стабло (или префиксно стабло) је структура података у облику стабла оптимизована за руковање низовима знакова, посебно корисна при раду са речницима речи, системима за аутоматско довршавање или префиксним претрагама.

У тројцу, сваки чвор обично представља један знак, а путање од корена до одређених чворова означавају целе речи . Чворови који се завршавају у речима су обично означени на неки начин (на пример, Буловим индикатором) како би се разликовали од једноставних префикса.

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

Уобичајене операције и проблеми са тријевима укључују: бројање колико је речи сачувано , исписивање свих речи у лексикографском редоследу, сортирање елемената низа уметањем у триј, генерисање валидних речи из скупа слова или изградњу структура сличних Т9 речнику.

У контекстима интервјуа, то није најосновнија структура коју ће тражити, али се редовно појављује у компанијама које раде са системима за претрагу, обраду текста или сугестије.

Хеш табеле и хеширање

Хеширање је техника додељивања нумеричког кључа (хеша) сваком податку на детерминистички начин, тако да можемо да чувамо и преузимамо елементе у готово константном времену, користећи тај кључ као индекс у интерној структури, обично низу.

Хеш табела је структура података која користи овај механизам. Сваки елемент се чува као пар кључ-вредност: кључ се трансформише у индекс табеле помоћу хеш функције, а вредност (или референца на њу) се тамо чува. Касније, да бисте претражили, једноставно поново хеширајте кључ и приступите одговарајућој позицији.

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

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

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

Како су алгоритми и структуре података повезани

Избор структуре података директно одређује који алгоритми имају смисла и колико ће бити сложени. Линеарни алгоритам претраживања на неуређеној листи обилази елементе један по један; ако променимо структуру у уравнотежено стабло претраживања или хеш таблицу, постижемо много брже резултате.

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

Насупрот томе, приликом дизајнирања алгоритма, често схватате да су вам потребна одређена својства: приступ индексу, брзо уметање на почетку, хијерархијски обиласци, претрага префикса итд. Ове потребе воде ваш избор структуре: низови, листе, стабла, графови, хеш табеле, петље „испробај“ и тако даље.

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

Стога, савладавање алгоритама и структура података није готово неопходан захтев за свакога ко тежи да постане компетентан и конкурентан програмер на данашњем тржишту рада.

Како научити структуре података и алгоритме

Многи људи се осећају заглављено када покушавају да сами уче помоћу платформи попут LeetCode-а или Codewars-а . Уобичајено је да почну са „лаким“ вежбама и даље не знају одакле да почну, на крају гледајући у решење и не знајући како да га касније репродукују.

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

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

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

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

За интервјуе је препоручљиво прегледати не само структуре већ и алгоритме грубе силе и повезане класичне алгоритме (обилазак, претрага, сортирање, једноставно враћање уназад, основно динамичко програмирање) и уверити се да можете наглас објаснити зашто сте изабрали одређену структуру и која је сложеност вашег решења.

Временом и уз мало истрајности , оно што на први поглед делује као зид, на крају постаје скуп познатих алата које користите готово инстинктивно када се суочите са новим проблемима.

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