Algoritme & struktura të dhënash

Si zgjidhen problemet me kod në mënyrë të zgjuar — lënda kryesore në fakultet, olimpiada dhe intervista pune. · 63 terma

A* pathfinding

Algoritmi A*

A* është si Dijkstra, por me një „hamendësim të zgjuar“ (heuristikë) se sa larg është destinacioni — kështu kërkon së pari në drejtimin e duhur. Përdoret shumë në lojëra, që personazhet të gjejnë rrugën.

Adjacency list & matrix

Lista dhe matrica e fqinjësisë

Një graf ruhet në kod në dy mënyra: lista e fqinjësisë (për çdo nyje, lista e fqinjëve të saj) — e mirë për grafe me pak lidhje — ose matrica e fqinjësisë (tabelë po/jo për çdo çift) — e mirë kur lidhjet janë shumë.

Algorithm

Algoritëm

Algoritmi është një listë hapash të qartë, njëri pas tjetrit, për të zgjidhur një problem. Para se të shkruash kod, shpesh e mendon algoritmin: çfarë duhet bërë dhe me çfarë radhe.

Amortized analysis

Analiza mesatare në kohë

Disa veprime janë zakonisht shumë të shpejta, por herë pas here shumë të ngadalta — p.sh. shtimi në një listë dinamike kur duhet të zmadhohet. Analiza „amortized“ e llogarit koston mesatare gjatë shumë veprimeve: shtimi mbetet O(1).

Anagram

Anagrami

Dy fjalë janë anagrame nëse kanë saktësisht të njëjtat shkronja në rend tjetër — „sorra“ dhe „roras“. Kontrollohet duke i renditur shkronjat ose duke i numëruar me një fjalor.

B-tree

B-tree është një pemë ku çdo nyje mban shumë vlera dhe ka shumë fëmijë, që pema të jetë shumë e ulët. Kështu duhen pak lexime nga disku — prandaj pothuajse çdo databazë i ndërton indekset e saj si B-tree.

Backtracking

Kthimi prapa

Backtracking ndërton një zgjidhje hap pas hapi dhe, sapo kupton se rruga s'të çon askund, kthehet një hap prapa dhe provon tjetrën. Përdoret për sudoku, labirinte dhe problemin e 8 mbretëreshave.

Balanced trees (AVL, red-black)

Pemët e balancuara

Nëse në një pemë kërkimi i shton numrat me radhë (1, 2, 3…), ajo bëhet një vijë e gjatë dhe kërkimi ngadalësohet në O(n). Pemët vetë-balancuese si AVL dhe red-black e rirregullojnë veten që të mbeten të shkurtra. TreeMap dhe std::map i përdorin.

Base case

Rasti bazë

Çdo funksion rekursiv ka nevojë për një rast bazë — kushtin kur ndalet dhe s'e thërret më veten. Pa të, rekursioni s'mbaron kurrë dhe programi rrëzohet me „stack overflow“.

Best, worst & average case

Rasti më i mirë, më i keq dhe mesatar

I njëjti algoritëm mund të jetë i shpejtë ose i ngadaltë sipas të dhënave. Kërkimi linear e gjen menjëherë nëse elementi është i pari (rasti më i mirë), por i kalon të gjitha nëse s'ekziston (rasti më i keq). Zakonisht na intereson rasti më i keq.

Big O notation

Shënimi Big O

Big O tregon si rritet koha (ose memoria) që i duhet një algoritmi kur rriten të dhënat. O(1) do të thotë gjithmonë njësoj shpejt, O(n) rritet njësoj me të dhënat, O(n²) rritet shumë shpejt. Pyetet shpesh në intervistat teknike.

Binary search

Kërkim binar

Kërkimi binar e gjen shpejt një vlerë në një listë të renditur: shikon mesin, dhe nëse vlera që kërkon është më e vogël, vazhdon te gjysma e majtë, përndryshe te e djathta — duke e përgjysmuar çdo herë. Për një milion elemente mjaftojnë rreth 20 hapa.

Binary search tree (BST)

Pema binare e kërkimit

Në një pemë binare kërkimi, çdo vlerë në të majtë të një nyjeje është më e vogël, dhe çdo vlerë në të djathtë më e madhe. Kështu kërkimi, shtimi dhe heqja bëhen në O(log n) — për sa kohë pema mbetet e balancuar.

Binary tree

Pema binare

Një pemë binare është pemë ku çdo nyje ka maksimumi dy fëmijë — majtas dhe djathtas. Është baza e shumë strukturave të tjera: pemëve të kërkimit, heap-eve dhe pemëve të shprehjeve matematikore.

Breadth-first search (BFS)

Kërkimi në gjerësi

BFS e eksploron një graf nivel pas niveli: së pari të gjithë fqinjët e afërt, pastaj fqinjët e tyre, e kështu me radhë, duke përdorur një radhë (queue). Në grafe pa pesha, gjen rrugën më të shkurtër.

Brute-force approach

Zgjidhja me forcë

Zgjidhja me forcë i provon të gjitha mundësitë një nga një. Është e lehtë për t'u shkruar dhe gjithmonë e saktë, por shpesh shumë e ngadaltë. Shpesh fillon me të, dhe pastaj kërkon një ide më të zgjuar.

Bubble sort

Renditja me flluska

Bubble sort krahason vazhdimisht çifte fqinjësh dhe i ndërron nëse janë në rend të gabuar, derisa elementet e mëdha „ngjiten“ në fund si flluska. E thjeshtë për t'u kuptuar, por e ngadaltë: O(n²).

Counting sort

Renditja me numërim

Kur vlerat janë numra të vegjël (p.sh. notat 1–5), counting sort thjesht numëron sa herë shfaqet secila dhe i shkruan me radhë. Punon në O(n) — më shpejt se çdo renditje me krahasime.

Data structure

Strukturë të dhënash

Struktura e të dhënave është mënyra si i organizon të dhënat në kod, që t'i gjesh dhe t'i ndryshosh lehtë — p.sh. listë, dictionary, stack, pemë. Zgjedhja e strukturës së duhur e bën programin shumë më të shpejtë.

Depth-first search (DFS)

Kërkimi në thellësi

DFS ecën sa më thellë në një degë të grafit para se të kthehet prapa dhe të provojë degën tjetër — me rekursion ose me një stack. Përdoret për labirinte, për të gjetur cikle dhe për renditje topologjike.

Dijkstra's algorithm

Algoritmi i Dijkstrës

Algoritmi i Dijkstrës gjen rrugën më të shkurtër nga një pikë te të gjitha të tjerat në një graf me distanca (pa vlera negative). Gjithmonë vazhdon nga vendi më i afërt që s'është vizituar ende, me një radhë me përparësi.

Divide and conquer

Ndaj dhe sundo

„Ndaj dhe sundo“ e ndan një problem të madh në copa më të vogla të të njëjtit lloj, i zgjidh ato (shpesh me rekursion) dhe i bashkon përgjigjet. Merge sort, quicksort dhe kërkimi binar punojnë kështu.

Doubly linked list

Lista e lidhur dyfishe

Në një listë të lidhur dyfishe, çdo nyje di edhe të mëparshmen, jo vetëm të ardhshmen. Kështu mund të ecësh në të dy drejtimet dhe ta heqësh një nyje shpejt. Butonat „Prapa“ dhe „Para“ të shfletuesit mund të ndërtohen kështu.

Dynamic array

Vargu dinamik

Një varg dinamik (si list i Python-it, ArrayList i Java-s, vector i C++) rezervon pak vend shtesë; kur mbushet, krijon një varg dy herë më të madh dhe i kopjon elementet. Kështu shtimi në fund mbetet mesatarisht O(1).

Dynamic programming

Programimi dinamik

Programimi dinamik e zgjidh një problem duke e ndarë në nënprobleme që përsëriten, dhe duke e ruajtur përgjigjen e secilit që të mos e llogarisë dy herë. Është teknika që e bën Fibonaccin(100) të menjëhershëm.

Factorial (n!)

Faktoriali

Faktoriali i n-së (n!) është prodhimi 1 × 2 × 3 × … × n — p.sh. 5! = 120. Tregon në sa mënyra mund të renditen n gjëra, dhe rritet jashtëzakonisht shpejt: 20! ka 19 shifra. Ushtrim klasik për rekursionin.

Fast exponentiation

Fuqizimi i shpejtë

Për të llogaritur aⁿ, në vend që të shumëzosh a me veten n herë, e ngre në katror dhe e përgjysmon n-në — vetëm rreth log n hapa. Përdoret në kriptografi dhe gara, shpesh me modul: pow(a, n, m) në Python.

Fibonacci sequence

Vargu i Fibonaçit

Vargu i Fibonaçit fillon me 0 dhe 1, dhe çdo numër tjetër është shuma e dy të mëparshmëve: 0, 1, 1, 2, 3, 5, 8, 13… Është shembulli klasik për rekursionin — dhe për të treguar pse rekursioni pa memoization është shumë i ngadaltë.

GCD (Euclidean algorithm)

Pjesëtuesi më i madh i përbashkët

Algoritmi i Euklidit gjen pjesëtuesin më të madh të përbashkët (PMP) të dy numrave duke e zëvendësuar vazhdimisht numrin e madh me mbetjen e pjesëtimit. Është nga algoritmet më të vjetra në botë — mbi 2000 vjet.

Graph (data structure)

Graf

Grafi është një strukturë me nyje të lidhura me vija (lidhje) — si një rrjet. Përdoret për rrjetet sociale (kush e njeh kë), për hartat (cilat qytete lidhen) dhe për të gjetur rrugën më të shkurtër.

Greedy algorithm

Algoritmi lakmitar

Një algoritëm „lakmitar“ zgjedh në çdo hap atë që duket më e mira tani, pa menduar për të ardhmen. Ndonjëherë jep zgjidhjen perfekte (p.sh. kthimi i kusurit me monedhat euro), ndonjëherë jo.

Hash collision

Përplasja e hash-it

Një përplasje ndodh kur dy vlera të ndryshme marrin të njëjtin hash dhe duan të njëjtin vend në tabelë. Tabelat hash e zgjidhin duke mbajtur një listë të vogël në atë vend (chaining) ose duke kërkuar vendin tjetër të lirë.

Hash function

Funksioni hash

Një funksion hash e kthen çdo vlerë (një fjalë, një skedar) në një numër me madhësi të fiksuar. E njëjta hyrje jep gjithmonë të njëjtin hash. Tabelat hash e përdorin për të ditur ku ta ruajnë një element; siguria e përdor për fjalëkalimet.

Hash table

Tabelë hash

Tabela hash është struktura që qëndron pas dictionary-ve dhe HashMap-ëve: një funksion hash e kthen çelësin në një numër që tregon menjëherë ku ruhet vlera. Prandaj kërkimi sipas çelësit është pothuajse i menjëhershëm, edhe me miliona elemente.

Heap

Grumbulli (heap)

Një heap është një pemë e veçantë ku prindi është gjithmonë më i vogël (min-heap) ose më i madh (max-heap) se fëmijët. Kështu elementi më i vogël merret në O(1) dhe shtimi/heqja bëhen në O(log n). Është baza e radhës me përparësi.

Heuristic

Heuristika

Një heuristikë është një rregull i zgjuar që gjen shpejt një zgjidhje „mjaft të mirë“, edhe pse jo gjithmonë më të mirën. Përdoret kur zgjidhja perfekte do të zgjaste shumë — p.sh. në GPS ose në lojëra.

Insertion sort

Renditja me futje

Insertion sort merr elementet një nga një dhe e fut secilin në vendin e duhur mes atyre që janë renditur tashmë. O(n²) në rastin e keq, por shumë e shpejtë kur lista është pothuajse e renditur.

Iterative vs recursive

Përsëritja dhe rekursioni

Shumë probleme mund të zgjidhen me cikël (iterativ) ose me një funksion që thërret veten (rekursiv). Rekursioni është shpesh më i lexueshëm për pemë dhe grafe; cikli zakonisht përdor më pak memorie dhe s'rrezikon stack overflow.

Linear search

Kërkimi linear

Kërkimi linear i kontrollon elementet një nga një derisa e gjen atë që kërkon. Punon në çdo listë, edhe të parenditur, por është O(n) — për lista të mëdha të renditura, kërkimi binar është shumë më i shpejtë.

Linked list

Listë e lidhur

Lista e lidhur është një strukturë të dhënash ku çdo element (nyje) mban vlerën e vet dhe një „tregues“ drejt elementit të radhës. Shtimi dhe heqja janë të shpejta, por për të arritur te elementi i 100-të duhet të kalosh nëpër të gjithë të mëparshmit.

LRU cache

Një cache LRU (Least Recently Used) mban vetëm N elementet e përdorura së fundmi; kur mbushet, hedh atë që s'është përdorur prej më shumë kohësh. Ndërtohet me një tabelë hash dhe një listë të lidhur dyfishe — pyetje klasike në intervista.

Memoization

Memorizimi i rezultateve

Memoization do të thotë ta mbash mend rezultatin e një funksioni për çdo hyrje, që herën tjetër ta kthesh menjëherë. Në Python e bën me @lru_cache. Është „versioni nga lart poshtë“ i programimit dinamik.

Merge sort

Renditja me bashkim

Merge sort e ndan listën përgjysmë vazhdimisht derisa çdo pjesë ka një element, pastaj i bashkon pjesët e renditura dy nga dy. Gjithmonë O(n log n) dhe e qëndrueshme — shembulli klasik i „ndaj dhe sundo“.

Minimum spanning tree

Pema minimale e shtrirjes

Pema minimale e shtrirjes i lidh të gjitha pikat e një grafi me koston totale më të vogël, pa cikle. Algoritmet e Kruskal-it dhe Prim-it e gjejnë. Përdoret për të planifikuar rrjete kabllosh, rrugësh ose ujësjellësi.

P vs NP & NP-complete

P kundrejt NP

Disa probleme zgjidhen shpejt (P). Për të tjerat — si gjetja e rrugës më të shkurtër që kalon nëpër 50 qytete — s'njihet asnjë metodë e shpejtë, edhe pse një zgjidhje kontrollohet lehtë (NP). Nëse P = NP është një nga pyetjet më të mëdha të pazgjidhura në matematikë.

Palindrome

Palindromi

Një palindrom lexohet njësoj nga e majta dhe nga e djathta — „radar“, „kapak“, 12321. Kontrolli i palindromit është ushtrim klasik për fillestarët me tekst, cikle dhe dy tregues.

Prefix sums

Shumat paraprake

Me shumat paraprake, llogarit një herë shumën nga fillimi deri te çdo pozicion. Pastaj shumën e çdo pjese të listës e merr në një hap: p[j] - p[i]. Shumë e dobishme në gara programimi.

Quicksort

Renditja e shpejtë

Quicksort zgjedh një element „pivot“, i vendos më të vegjlit majtas dhe më të mëdhenjtë djathtas, dhe pastaj e përsërit për secilën anë. Mesatarisht O(n log n) dhe shumë i shpejtë në praktikë; me pivot të keq mund të bëhet O(n²).

Recursion

Rekursion

Rekursioni ndodh kur një funksion e thërret veten, çdo herë me një problem pak më të vogël, derisa arrin një rast aq të thjeshtë sa ta zgjidhë menjëherë. Pa këtë „rast bazë“, funksioni do të vazhdonte pafundësisht.

Segment tree & Fenwick tree

Pema e segmenteve

Pema e segmenteve dhe pema Fenwick ruajnë informacion për copa të një liste, që t'u përgjigjen shpejt pyetjeve si „sa është shuma nga pozicioni 3 te 8?“ edhe kur lista ndryshon shpesh — të dyja në O(log n). Shumë të përdorura në gara.

Selection sort

Renditja me zgjedhje

Selection sort gjen elementin më të vogël dhe e vendos në fillim, pastaj më të voglin nga ata që mbetën, e kështu me radhë. Gjithmonë O(n²), por bën pak ndërrime.

Sieve of Eratosthenes

Sita e Eratostenit

Sita e Eratostenit gjen të gjithë numrat e thjeshtë deri në N: fillon nga 2 dhe fshin të gjithë shumëfishat e tij, pastaj kalon te numri tjetër i pa fshirë, e kështu me radhë. Ata që mbeten janë të thjeshtë.

Sliding window

Dritarja rrëshqitëse

Te dritarja rrëshqitëse, shikon një „copë“ të listës me gjatësi të caktuar dhe e lëviz një hap në çdo radhë, duke shtuar elementin e ri dhe hequr të vjetrin — në vend që ta rillogaritësh gjithë copën nga e para.

Sorting algorithm

Algoritëm renditjeje

Algoritmet e renditjes i vendosin elementet në rregull — p.sh. numrat nga më i vogli te më i madhi. Ka shumë mënyra: bubble sort është e thjeshtë por e ngadaltë, quick sort dhe merge sort janë shumë më të shpejta. Në praktikë përdor sorted() të gatshëm.