07_razeni

Třídění a vyhledávání 

Přednáška 7 

rev 2019.2 

Motivace 

• velké soubory dat 

častý požadavek je získat určitá data 
jak je obtížné vyhledat určitá data 

• v nesetříděném souboru dat? 
• v setříděném souboru dat? 

dokážete stanovit obtížnost přístupu? 

• pro vyhledávání je lepší mít data seřazená 
• různé metody řazení 
• rozdílný přístup pro 

• řazení neseřazeného pole 
• a pro přidávání dalších prvků do seřazených dat 

Motivace 

• kolik operací je potřeba pro seřazení čtyř prvků? 

• počítáme nejhorší variantu 
• 6 porovnání (N.(N-1)/2 ) 
• 0-6 přesunů (výměn) hodnot 

• průměrný čas přístupu je cca N/2. 
• u setříděného pole je to půlení intervalu 

• tj maximálně log2 N 
• pro 4 prvky = max 2 pokusy, ale pro polovinu prvků to 

bude rychlejší 

• N mohou být ve skutečnosti tisíce, miliony položek 

Motivace 

• pro vložení do seřazeného pole 

• bude záležet na směru řazení 
• v našem případě až 4 porovnání 
• k tomu až N výměn 

• čím méně porovnání (prvek je více vlevo) 
• tím více přesunů 
počet operací je „konstantní“ 

Složitost algoritmů 

• slouží například k 

• hodnocení 

• porovnání vhodnosti algoritmů 

• rozlišujeme 

• časovou 

• paměťovou 

• někdy lze určit přesně 

• přístup k x-tému prvku v poli nebo lineárním seznamu 

• někdy pouze statisticky 

• střední doba 

• řazení dat může trvat pro různé datové sady různě  

• Často se však uvádí nejhorší možný výsledek složitosti 

Složitost algoritmů 

• kolik kroků je potřeba k získání x-tého prvku v poli? 

• 1 kroků 

• kolik kroků je potřeba pro získání x-tého prvku 

v lineárním seznamu?