Složitost algoritmu
Z MiS
(Rozdíly mezi verzemi)
(→Složitost jako míra pro srovnání algoritmů: Měření složitosti jako samostatná kapitola.) |
m (→Asymptotická složitost: Oprava vzhledu) |
||
| Řádka 31: | Řádka 31: | ||
*Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat. | *Jakým způsobem se složitost algoritmu (počet operací) mění při změně objemu vstupních dat. | ||
*Zapisujeme <code>O(f(N))</code> | *Zapisujeme <code>O(f(N))</code> | ||
| − | **N... velikost dat | + | ** <code>N</code>... velikost dat |
| − | **f(N)... funkce, jejímž růstem lze limitovat růst počtu operací | + | ** <code>f(N)</code>... funkce, jejímž růstem lze limitovat růst počtu operací |
| − | **Pokud je velikost vstupu N, pak je složitost limitována funkcí <code>A+B.f(N)</code> | + | **Pokud je velikost vstupu <code>N</code>, pak je složitost limitována funkcí: <code>y = A+B.f(N)</code> |
;Příklady růstu počtu operací | ;Příklady růstu počtu operací | ||
| − | *O(N) — lineární | + | * <code>O(N)</code> — lineární |
*Lepší než lineární | *Lepší než lineární | ||
| − | **O(log(N)) | + | ** <code>O(log(N))</code> |
| − | **O(sqrt(N)) | + | ** <code>O(sqrt(N))</code> |
| − | *O(N.log(N)) | + | * <code>O(N.log(N))</code> |
| − | *O(N<sup>2</sup>) — kvadratický | + | * <code>O(N<sup>2</sup>)</code> — kvadratický |
| − | *O(N<sup>3</sup>) — kubický | + | * <code>O(N<sup>3</sup>)</code> — kubický |
*Polynomiální | *Polynomiální | ||
| − | **roste jako libovolný polynom (omezen O(N<sup>i</sup>), kde i je lib. konstanta). | + | **roste jako libovolný polynom (omezen <code>O(N<sup>i</sup>)</code>, kde <code>i</code> je lib. konstanta). |
| − | *O(2<sup>N</sup>) — exponenciální | + | * <code>O(2<sup>N</sup>)</code> — exponenciální |
** 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]. | ||
| − | + | <div class="Priklad">Úkol: Navrhněte algoritmus a odhadněte složitost | |
* Hledání maxima | * Hledání maxima | ||
| + | </div> | ||
== Související pojmy == | == Související pojmy == | ||
Verze z 25. 9. 2014, 10:29
Obsah |
Složitost jako míra pro srovnání algoritmů
Hledáme nástroje pro porovnání efektivity algoritmů.
- Máme
Nprvků vstupních dat (Nzá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,
- ...
Měření složitosti
- Neměříme čas, ale počet operací!
- Tím omezíme vliv konkrétního HW.
- Nepočítáme všechny dílčí operace!
- 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, procesorové architektury,...
- Zajímají nás velká data, řádový růst!
- Viz asymptotická složitost.
- Malé instance skončí v rozumném čase, i když se budou počítat neefektivně.
- Zajímá nás maximální nebo průměrná složitost!
- Tím eliminujeme vliv konkrétního 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í:y = 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), kdeije lib. konstanta).
- roste jako libovolný polynom (omezen
-
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
