Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
(Vytvoření stránky) |
m (Přidán odkaz na Algoritmus) |
||
Řádka 3: | Řádka 3: | ||
== Složitost jako míra pro srovnání algoritmů == | == Složitost jako míra pro srovnání algoritmů == | ||
Hledáme nástroje pro porovnání efektivity algoritmů. | Hledáme nástroje pro porovnání efektivity algoritmů. | ||
− | * | + | *Máme <code>N</code> prvků vstupních dat (<code>N</code> zákazníků, <code>N</code> čísel,...), |
− | *zajímá nás, který ze dvou algoritmů vrátí výsledek dříve | + | *zajímá nás, který ze dvou algoritmů vrátí výsledek dříve. |
− | + | <div class="Poznamka">Rychlejší algoritmus → lepší algoritmus!</div> | |
− | ;Problém | + | ;Problém — čas je ovlivněn: |
* volbou konkrétního zadání stejného problému, | * volbou konkrétního zadání stejného problému, | ||
− | * výkonem počítače, | + | * výkonem počítače (pozor také na další běžící procesy), |
* kvalitou implementace algoritmu, | * kvalitou implementace algoritmu, | ||
* použitým programovacím jazykem, | * použitým programovacím jazykem, | ||
Řádka 16: | Řádka 16: | ||
; Zjednodušení: | ; Zjednodušení: | ||
− | * | + | *Neměříme čas, ale počet operací (tím omezíme vliv HW). |
*Nepočítáme všechny instrukce | *Nepočítáme všechny instrukce | ||
**obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk. | **obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk. | ||
Řádka 28: | Řádka 28: | ||
**N... velikost dat | **N... velikost dat | ||
**f(N)... funkce, jejímž růstem lze limitovat růst počtu operací | **f(N)... funkce, jejímž růstem lze limitovat růst počtu operací | ||
− | **Pokud je velikost vstupu N, pak je složitost limitována funkcí A+B.f(N) | + | **Pokud je velikost vstupu N, pak je složitost limitována funkcí <code>A+B.f(N)</code> |
;Příklady růstu počtu operací | ;Příklady růstu počtu operací | ||
Řádka 43: | Řádka 43: | ||
** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže]. | ** Viz například: [http://cs.wikipedia.org/wiki/Hanojsk%C3%A9_v%C4%9B%C5%BEe Hanoiské věže]. | ||
− | ; Úkol | + | ; Úkol — Navrhněte algoritmus a odhadněte složitost |
* Hledání maxima | * Hledání maxima | ||
Řádka 49: | Řádka 49: | ||
; Složitost problému | ; Složitost problému | ||
*Složitost nejlepšího algoritmu, který řeší daný problém. | *Složitost nejlepšího algoritmu, který řeší daný problém. | ||
− | *× složitost nejlepšího | + | *× složitost nejlepšího ''známého'' algoritmu. |
; Maximální × průměrná složitost | ; Maximální × průměrná složitost | ||
Řádka 56: | Řádka 56: | ||
; Paměťová × časová složitost | ; Paměťová × časová složitost | ||
+ | |||
+ | == Viz také == | ||
+ | * [[Algoritmus]] | ||
== Zdroje == | == Zdroje == | ||
*[http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost Wikipedia.org > Asymptotická složitost] | *[http://cs.wikipedia.org/wiki/Asymptotick%C3%A1_slo%C5%BEitost Wikipedia.org > Asymptotická složitost] |
Verze z 17. 10. 2013, 11:57
Obsah |
Složitost jako míra pro srovnání algoritmů
Hledáme nástroje pro porovnání efektivity algoritmů.
- Máme
N
prvků vstupních dat (N
zákazníků,N
čísel,...), - zajímá nás, který ze dvou algoritmů vrátí výsledek dříve.
Rychlejší algoritmus → lepší algoritmus!
- Problém — čas je ovlivněn
- volbou konkrétního zadání stejného problému,
- výkonem počítače (pozor také na další běžící procesy),
- kvalitou implementace algoritmu,
- použitým programovacím jazykem,
- použitými knihovnami,
- ...
- Zjednodušení
- Neměříme čas, ale počet operací (tím omezíme vliv HW).
- Nepočítáme všechny instrukce
- obvykle počítáme pouze „významné“ (časově náročné) operace (počet porovnání, počet přístupů na disk.
- Tím eliminujeme vliv použitého překladače, knihoven, jazyka,...
- Zajímají nás velká data, řádový růst (viz asymptotická složitost).
- Zajímá nás maximální nebo průměrná složitost. (Eliminujeme vliv zadání.)
Asymptotická složitost
- Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat.
- Zapisujeme
O(f(N))
- N... velikost dat
- f(N)... funkce, jejímž růstem lze limitovat růst počtu operací
- Pokud je velikost vstupu N, pak je složitost limitována funkcí
A+B.f(N)
- Příklady růstu počtu operací
- O(N) — lineární
- Lepší než lineární
- O(log(N))
- O(sqrt(N))
- O(N.log(N))
- O(N2) — kvadratický
- O(N3) — kubický
- Polynomiální
- roste jako libovolný polynom (omezen O(Ni), kde i je lib. konstanta).
- O(2N) — exponenciální
- Viz například: Hanoiské věže.
- Úkol — Navrhněte algoritmus a odhadněte složitost
- Hledání maxima
Související pojmy
- Složitost problému
- Složitost nejlepšího algoritmu, který řeší daný problém.
- × složitost nejlepšího známého algoritmu.
- Maximální × průměrná složitost
- viz QuickSort
- Aneb: Pojedete do školy o 4 hodiny později proto, že v nejhorším možném případě Vám cesta bude trvat pěšky 4 hodiny?
- Paměťová × časová složitost