07_razeni
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
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?