ALG Flashcards
(40 cards)
Asymptoticky rust/odhad runkce
- Horni - velke O
- f(n) je tridou O(g(n)), tedy funcike g shora odhaduje f az na konstantnu
- (Ex c>0)(Ex n0)(ProVse n > n0) plati: f(n) <= c * g(n)
- tedy od nejakeho pocatecniho indexu je funkce f mensi nebo rovna nasobku funkce g
- funkce g muze byt klidne stejneho radu, nebo dokonce mensi na nejakem intervalu, (nebo dokonce na celem intervalu - treba 3x je shora ohranicene funkce x, protoze staci vzit c=4 a najednou 3x je shora ohranicenej 4x…) ale od urciteho indexu (limitne) je rychlejsi - Dolni odhad - velka Omega
- stejny princip, jina nerovnost pouze - Optimalni odhad - velka Theta
- funkce je optimalne odhadnuta druhou funkci, pokud je ji shora i zdolaomezena
- a plati to i naopak
- (Ex c1, c2>0)(Ex n0)(ProVse n > n0) plati: c1*g(n) <= f(n) <= c2 * g(n)
Rust funkce (polynomu) urcuje clen s nejvetsi mocninou
Limitni kriteria:
1. lim f/g = 0, pak f je shora ohranicene g
2. lim f/g = c, pak f je optimalni vuci g a naopak
3. lim f/g = nekonecno, pak je shora odhaduje g
Prefixni suma
Pokud mam nejake pole A[] a chci rychle v case O(1) spocitat sumu pouze nejakeho poduseku. Abych to umel, zavedu pomocne prefixni pole P[], kde P[i] = Summa(a0, …, ai), tedy je to suma do tohoto useku.
Pokud pak chci spocitat hned sumu poduseku A, tak vezmu pocatecni undex a koncovy a spocitam to jako: P[konec] - P[pocatek]
Da se rozsirovat i pro 2D matice, kde mam obdelnik ktery mi uderzuje castecne soucty uvnitr podmatice…
Co plati pro asympt. rust logaritmickych funkci o ruznych zakladech?
Rostou stejne podle jsite vety. Navic jakakoliv mocnina logaritmu je VZDY SHORA OHRANICENA LINEARNI FUNKCI
Rozdel a panuj obecne, vyuziti, vzroec casove narocnosti
Kdyz chce velky problem rozdelit na mensi subproblemy ktery predam rekurzivne dal kde se zpracuji na elementarni/atomicke urovni (treba razeni - quicksort)
Tedy cas ulohy je = 1/2 casu + 1/2 casu + atomicka_uprava
T(n) = T(n/2) + T(n/2) + Theta(n), pro n elementarnich uprav v ramci atomickeho kroku
Mistrovska veta
Pro ihned urceni casove narocnosti rekurzivnich algoritmu tvaru:
T(n) = aT(n/b) + f(n), tedy a-krat rozdelime ulohu na n/b poduloh a pricteme nejakou atomickou upravu
- Pokud f(n) je O(n^(logb(a))) potom
- T(n) je Theta(n^(logb(a))), tedy funkce se chova podle prvniho clenu
- Pokud f(n) je Theta(n^(logb(a))) potom
- T(n) je Theta(n^(logb(a)) * log(n)), tedy prvni a druhy clen jsou si rovny -> oba se podili na asymptotickem rustu funkce
- Pokud f(n) je Omega(n^(logb(a) + epsilon)) pro epsilon > 0 A POKUD af(n/b) <= cf(n) pro c < 1 a dostatecna velka n, potom
- T(n) je Theta(f(n), tedy druhy clen prevalcoval ten prvni a jen on prispiva do as. slozitosti
Hloubka rek. stromu a pocet listu
Hloubka - podle toho, jak delim data, na jaky kusy: n/2 => log2n, n/3 => log3n, n/7 => log7n…
Tedy hloubka je logaritmus n o zakladu deleni na kusy
Pocet listu je n^hloubka (asymptoticky, muze byt treba o 1 min a tak…)
Treba n^(log7(n)), kam za n dosazuju pocet volani rekurze.
Obecne:
T(n) = a*T(n/b) + f(n)
- hloubka = logb(n)
- pocet listu = n^hloubka = n^logb(a) => dosazdim tedy a
Co je binarni, pravidelny binarni a vyvazeny binarni strom?
Binarni - ma max 2 potomky
Pravidelny binarni - ma bud 0 , nebo 2 potomky (ne 1)
Vyvazeny binarni strom - zaplnuje se zleva doprava pravidelne bez der, jeho hloubka pro n uzlu je log2(n+1) - 1
Reprezentace uzlu v kodu a pruchody in/pre/post order
class Node {
int value;
Node left;
Node right;
}
Obecne zpracovani stormu rekurzivne:
void rec_tree(Node node){
(if node == null) return;
rec_tree(node.left);
rec_tree(node.right);
}
3 zpusoby v jaky moment zpracovat uzel node
1. Preorder - hned na zacatku, pred volanim dalsim rekurzi do potomku, vypis ukazuje presnou trajektorii pruchodu
2. Inorder - nejvic levej potomek, tedy nejdriv se zahlubim do nejvic vlevo potomka, pak ho vypisu a jdu do pravych potomku, vypisuje to binarni storm zleva doprava po uzlech jako projekce
3. Postorder - kdyz uz nemam potomky a vracim se tak vypisu uzel, tedy potomci jsou vypsani driv nez predek
Pocitani uzlu a hloubky, nejdelsi cesta
spocit(vlevo) + spocti(vravo) + 1,
max(hloubka(vlevo), hloubka(vpravo)) + 1
cesta(vlevo) + cesta(vpravo) + 2
Backtreking
Prohledavani stavoveho prostoru v navratem. Tedy prochazim strom do hloubky a vzdy na rozcesti zkusim jednu moznost, poznamenam si stav, abych ho pak mohl obnovit, zkusim to tam, pak se vratim, obnovim stav, zkusim jinou moznost atd… tedy postupne predavam stav a obnovuju ho, treba umisteni dam na sachovnici - zkusim se zanorovat z jednoho policka a koukam zda damu tam mohu umistit a jakmile uz ne, tak ze vracim zpet o krok vys ale musim si pamatovat i stav ze ktereho jsem vychazel
Mohu u toto urezavat stavovy prostor tak, ze se nevydam cestou ktera je pro me dopredu znama jako nevyhodna a hned se vracim
Reprezentace grafu v pameti dva pristupy
- Matice incidence (slozite na pamet)
- Seznam sousedu kazdeho uzlu
BFS
Breadth-First-Search, pruchod grafem do sirky. Prochazi graf po patrech potomku ferove, tedy nezanoruje se do nejake strany, ale rovnomerne bere hladiny stromu a prochazi je treba zleva doprava po patrech.
Pracuje s frontou (FIFO) datova struktura.
1. Pridej koren do fronty
2. Dokud fronta neni prazdna tak proved:
3. Pop()
4. Zpracuj to cos vyndal
5. Pridej jeho potomky
Slozitost je n, protoze proste musim projit vsechny uzly
DFS je taky lineaerni slozitost
Vyuziti - hledani komponent souvislosti (fronta je empty, ale nebyl jsem ve vsech uzlech), hledani kruznice (znovuobjeveni nejakeho uzlu kde jsem byl enbo je ve fronte), hledani nejkratsi cesty tak, ze koren ma counter 0 a pri pridani jeho sousedu do fronty (objeveni jeho sousedu) jim zvysim counter o 1 => pak tedy posledni uzel ma informaci o vzdalenosti od korene k nemu…
DFS
Prochazeni do hloubky. Slozitost je V+E jako BFS (???). Obycejna rekurze pres vsechny neobjevene sousedy dosud.
DFS(Node node):
node.visited = true
foreach n in node.neighbours do
if !n,visited then: DFS(n)
Takze vem node a pro kazdeho jeho souseda zpust rekurzivne DFS pokud nebyl objeven
Pouziti BFS, DFS
- Detekce komponent souvislosti
- Detekce cyklu - POUZE DFS (narazim na otevreny uzel, tedy jsem se do nej vratil cyklme), BFS najde kruznice
- Nalezeni kostry
- Nejkratsi cesta - POUZE BFS
- Topologicke usporadani - POUZE DFS (sestupne usporadam podle casu uzavreni)
Vyhledavani v serazenem poli
Pomoci Binary Search, kdy pole pulime na interaly poloviny a kontrolujeme zda moje hodnota lezi v tomto intervalu.
Vyuziva BST - strom ktery reprezentuje serazene hodnoty. Logaritmicka narocnost
Exponencialni vyhledavani - navysuju hledany interval tak dlouho, dokud tam nespadne mnou hledana hodnota - tedy nejdruv exponencialne hledam interval a pak az v nem treba nasadim binary search
BST
Datova struktura reprezentujici usporadane pole prvku pro vyhledavani. Inorder vypise serazene pole.
Leva cast - mensim prava - vetsi
Find:
jestli jsem tento uzel - vrat
jestli jsem mensi nez hledana hodnota - hledej vpravo
jestli jsem vetsi nez hledana hodnota - hledej vpravo
Insert:
1. find misto
2. vytvor novy uzel a napoj ho
Delete uzel (se dvema potomky)
1. Find ho
2. Najdi k nemu nejblizsi vetsi vpravo
3. Dej nejblizsi vyssi vpravo na misto smazaneho
4. Preusporadej potomky noveho uzlu
Asymptoticka slozitost operaci BST
OBECNY BST MUZE BYT RETIZEK HODNOT!
- tedy Find, Insert, Delete obecne jsou Theta(n) kdy musime vzdy projit pole prvku velikosti n
Vyvazeny BST strom je stromovity takze je to log(n)
AVL Strom
Binarni Vyhledavajici Strom splnujici podminku:
- pro kazdy uzel je rozdil hloubek leveho a praveho podstrmomu roven -1, 0, nebo 1.
Jakmile dojde k poruseni podminky, tak se strom musi vybalancovat rotacemi.
Je to vyvazeny strom, udrzuje stromovitou strukturu porad, proto operace v nem jsou Theta(logn) oproti obecnemu BVS
Rotace - uzel ktery putuje nahori preda svoje potomky uzlu ktery se snizuje.
Nekdy jendoducha rotace nemusi stacit a musime provest dvojitou rotaci. Od pridaneho uzlu postupujeme smerem ke koreni a pokud narazime na rozvazeny uzel, tak se podivame na posledni dva kroky jak jsme tam dosli, (typicky pro root)
- prisli jsme dvakrat zprava/zleva - prava/leva rotace jednoducha
- prisli jsme zleva-zprava - provedeme nejdriv leva pak prava rotace
- prisli jsme zprava-zleva - provedeme nejdriv pravou pak levou rotaci
Po operaci insert staci VZDY POUZE JEDNA ROTACE
Po operace delete OBECNE AZ PO O(logn) rotacich
B=Strom
Pri databayovzch szstemech, souborovych systemech
B-Strom radu k ma bunky velikosti 2k a uchovav minimalne k nebo 2k klicu (krome korene, muze mit jen jeden klic treba).
Tedy stormr radu k=2 ma bunky velikost 4.
Uchovava v blocich prvky mensi nez na dane pozici
- kazdy uzel ma 1 vice potomku nez klicu
- vsechny cesty od korene k listum jsou stejne dlouhe
- find - sestupuju na hladinu klice a v ramci bunky uz hledam lienarne nebo binarne
Insert - najdi potrebnou pozici
- pokud je volne misto tak vloz
- pokud neni misto, tak usporadej mimo prvky
- vyber jejich median (prostredni prvek, vzdycky je, protoze rad je 2k sudy)
- z medianu udelej novej uzel, napoj na nej zleva prvky mensi a zprava prvky vetsi
- napoj novy uzel k rodici pokud jde
- pokud nejde opakuje stepeni rodicu…
Delete -
- najdi prvek a pokud ma dost klicu tak vymaz
- pokud mazes ve vnitrnim uzlu a ma dost klicu, tak ho nahrad nejblizsim prvekm z listu pokud ma dost klicu
- pokud ale by mel uzel min nez k klicu tak:
- spoj sousedni uzly spolu s jejich JEDINYM rodicem mezi nimi (sleju dohromady)
- jejich median poslu na misto rodice a PRELEJU OD sousedu nejake prvky pokud to jde, tedy prerotuju sousedni uzel aby se mi podelil o nekolik prvku
- pokud ani soused nema dost prvku - tak dva uzly spoj dohromady (slej do jednoho i vcetne rodice), vsechno dej do jednoho uzlu (vymaz ten prazdny) a vymaz i rodice z horni hladiny
Slozitost B-stromu radu K:
vsechny tri operace: Theta(k*logk(n)), tedy log je stoupani stromovou sturkturou a v ramci bunky musim projit linearni k prvku
Radici algoritmy obecne, n^2
Radici algoritmy sloui k serazeni pole (protoze v serazenem poli umime efektivne vyhledavat). Bud n^2, kde potrebujeme porjit cele pole a treba porovna kazde dva prvky v nem coz nam da dvojity for cyklus vuci n takze asymptoticky n^2 slozitost Theta.
- Selection sort
- Insert sort
- Bubble Sort
- Quick Sort pro predem serazena data casteccne
Selection sort
Radici algoritmus slozitossti n^2. Prochazime cele pole a pro kazdy prvek:
- najdeme minimum ve zbyvajici casti pole
- Porovname ho s aktualnim prvek na kterem stojime
- Bud je prohodime nebo nechame byt.
Tedy dvojity for cyklus prochazi cele pole a kazdy prvek s kazdym kdo je mensi, pokud jsem nasel mens, tak je prohodim na VEKLOU VZDALENOST
- nestabilni
- celkvoa slozitost Theta(n^2) nejde vylepsit ani zhorsit
- pocet porovnani - n(n-1)/2, tedy kazdy s kazdym
- za jednu operac 3 presuny pres tmp promennou, tedy celkem az 3(n-1) presunu pokud mam pole sereazeno treba uz sestupne tak se kazdy prvek prohodi
- vyhoda - malo zapisovnai do pameti a prohozeni
Insert Sort
Radici algoritmus sloziosti n^2.
- prochazime cele pole a vzdy nasledujici prvek zarazujeme do zleva jiz serazene podposloupnosti (insertujeme ho).
- Pro kazdy prvek v poli, pro usporadanou cast proved:
- Porovnej aktualni prvek ktery chceme insertovat s jiz serazenou casti vlevo
- Mensi prvky probublavaji treba az na uplny zacatek
- v nejlepsim pripade udelam pouze 1 test (nasledujici prvek je vetsi nez cela jiz vlevo serazena cast), tedy celkem (n-1) testu
- v nejhrosim pripade az k testu, kde k je veliksot srazene casti vlevo (pro pole treba sereazene sestupne), tedy celkem porovnam kazdeho s kazdym - n(n-1)/2
- presunu 2 v nejlepsim pripade (proste swap), tedy 2(n-1) prohozeni
- v nejhorsim pripade az k+1 prohozeni, tedy (n^2 + n - 2)/2 presunu
- vyhoda - skoro linearni pro serazeny vstup, stabilni
- slozitost SHORA OMEZENA O(n^2), muze byt i linearni
Bubble sort
Radici algoritmus, ktery vytvori okenko a prohodi dva sousedni prvky pokud je to potreba. Udela to pro celou delku pole. Tedy okenko se posouva (NE PRVEK ZAFIXOVANY) jeden prubeh okenanka prohodi sousedy 1. faze, pak to same se udela jeste jednou a jeste jednou… tedy okenko projede na konec a pak od zacatku znovu
- postupne se mi hromadi na kocni pole nejvetsi prvky
- vyhoda - jednoduchy kod, stabilni - prohozuje pouze dva sousedy vedlejsi
- pro kazdy prvek v pole
- pro kazdou dvojici
- porovnej a prohod
- celkem testu - kazdy s kazdym - n(n-1)/2
- celkem presunu - nejhorsi pripad n(n-n)/2 kvadraticka
- slozitost je Theta(n^2) nejde zrychlit
Quicksort
Algoritmus ktery radime do O(n^2) obecne, ale ocekavame nlogn slozitost.
- Zvolime pivota (bud nahode, nebo median prvku, nebo 1. prvke atd…)
- Rozdelime vstupni pole na male a velke prvky oproti pivotu (bud ostra nebo neostra neorvnost, pivota muzeme dat do jaekoliv poloviny)
- Zavedeme ukazatel zleva a zprava a zacneme u prvniho a posledniho prvku
- Vzdy kouknem na dva prvky podle uazatelu a porovnavame je
- pokud se maji prohodoit - prohodime je a posouvam ukazatele k sobe
- pokud se jen jeden ma prohodit, tak u nej ukazatel nechame a u druheho pokracujeme s posunem - Kdyz jsme dosli k tomu, ze se ukazatele protli -> volej rekurzi od kroku 1 na dve vznikle poloviny…
Tedy kod mi rozpuli vstupni pole na mensi podproblemy, kde v kazdem z nich rekurzivne to rozpulim dal, kde kazde deleni mi prehodi male prvky a velke prvky. Tedy v poslednim kroku se pouze proovnaji dve hodnoty a prohodi se podle velikost.
Nejhorsi pripad je ze si spatne zvolime pivota (nebo pole je uz serazene) a budeme pole delat na 1 prvek a zbytek - coz nam povede na lienarni zpracaovani pole n-krat - tedy Theta(n^2).
Obecne ale ocekavana slozitost je Theta(nlogn), protoze mam stromovitou strukturu jejichz hloubka je logn a v kazdem kroku udelame n porovnani.
- vyhody - muzeme ocekavat vetsi rychlost nez n^2, ve standardni knihovne vetsinou implementovan
- nevyhoda - nestabilni
- pocet rpesunu obecne- nlogn Theta
