07_razeni

• N kroků 

• dosažení cíle pro půlení intervalu 

• log2 N 
• log2 8 = 3 

Časová složitost 

• Big O notation 

• O – Order, řád funkce 

• může se udávat v počtu kroků 

• záleží na počtu dat (základních + pracovních) 

• může se lišit pro různé operace 

• seřazení 
• vyhledání 
• zjištění hodnoty 

• pro složitý vzorec  

• bere se nejvýrazněji rostoucí část součtu 
• například: 

• pro 10N^2+3N+50 
• můžeme uvést O(N^2)  

Časová složitost 

• O(1) 

• konstantní složitost 
• vyhledání prvku v poli pomocí indexu 

• O(N) 

• lineární složitost 
• vyhledání prvku v lineárním seznamu 
• suma N čísel v poli 

• O(N^2) 

• kvadratická 
• vyhledání maxima ve čtvercové matici 

• O(log2 N) 

• logaritmická 
• vyhledání pozice v seřazeném poli půlením intervalu 

Vyhledávání 

• náročnost 

• podle polohy hledané položky 

• uhodněte číslo na které myslím 

• normální vyhledávání 

• až N 

• binární vyhledávání 

• využívá půlení intervalu 
• složitost log2 N 

Vyhledávání 

• realizace 

• polem 
• lineárním seznamem 
• binárním stromem 

• výhody realizací 

• pro vyhledávání 
• pro vkládání 

Vyhledávání v poli 

• hledání extrému 

• maximum / minimum 
• v setříděném poli na kraji 
• v nesetříděném musíme projít celé pole 

• více stejných hodnot v poli 

• která z nich je ta požadovaná? 

• nejhorší případ 

• hledáme hodnotu, která v poli není 

• co když není přesná hodnota? 

• hledat menší 
• hledat větší 
• zahlásit chybu? 

Vyhledávání sekvenční 

• hledání pozice hodnoty v nesetříděném poli dat 

• postupně projít všechny prvky 

• vhodný pro malé vzorky dat 

• maximální O(n) 
• průměrná O(n/2)