GMLWiki

Uživatelské nástroje

Nástroje pro tento web

Historie: • Bitmapová grafika • Objektově orientované programování (OOP) • Značkovací jazyky • Datové typy strukurovaných jazyků • Digitalizace analogového signálu/zvuku • Komprese a šifrování • Sítě (technologie, topologie, HW) • Algoritmizace • Paměti, ukládání dat • Služby sítě: www, vyhledávání, sociální sítě
informatika:maturita:22a

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
Následující verze		Předchozí verze
informatika:maturita:22a [24. 04. 2015, 15.37] – xmrnustikinformatika:maturita:22a [28. 05. 2020, 15.10] (aktuální) – [Merge sort] xdostal
Řádek 1: Řádek 1:
 ====== Třídění/Řazení a vyhledávací algoritmy ====== ====== Třídění/Řazení a vyhledávací algoritmy ======
  
-===== Třídění vs řazení =====+===== Třídění vs. řazení =====
  
 Třídění je uspořádání objektů podle podobných vlastností. Způsob třídění je vždy závislý na oboru, který s těmito objekty pracuje. Třídění je uspořádání objektů podle podobných vlastností. Způsob třídění je vždy závislý na oboru, který s těmito objekty pracuje.
Řádek 7: Řádek 7:
 Řazení je způsob uspořádání objektů do specifikovaného pořadí. Řazení může být provozováno podle různých kritérií (abecedně, vzestupně, sestupně). Řazení je způsob uspořádání objektů do specifikovaného pořadí. Řazení může být provozováno podle různých kritérií (abecedně, vzestupně, sestupně).
  
-Tyto dva pojmy bývají často zaměňovány. +Oba pojmy bývají často zaměňovány.
  
 ===== Složitost algoritmů ===== ===== Složitost algoritmů =====
Řádek 17: Řádek 16:
 {{:informatika:maturita:22_slozitost_algoritmu.png|}} {{:informatika:maturita:22_slozitost_algoritmu.png|}}
  
-Rozdíl mezi jednotlivými třídami složitosti se dá jednoduše pochopit na těchto dvou příkladech. Když máme první algoritmus se složitostí O(n) a druhý algoritmus se složitostí O(2n) stačí nám ten druhý spustit na dvakrát rychlejším stroji a rozdíl je smazán. Pokud však máme první algoritmus se složitostí O(n) a algoritmus se složitostí O(n<sup>2</sup>) bude při různé velikosti stoupat náročnost v závislosti na n 10x, 20x,... +Rozdíl mezi jednotlivými třídami složitosti se dá jednoduše pochopit na těchto dvou příkladech. Když máme první algoritmus se složitostí O(n) a druhý algoritmus se složitostí O(2n) stačí nám ten druhý spustit na dvakrát rychlejším stroji a rozdíl je smazán. 
 + 
 +Pokud však máme první algoritmus se složitostí O(n) a algoritmus se složitostí O(n<sup>2</sup>) bude při různé velikosti stoupat náročnost v závislosti na n, a to několikrát.
  
-===== Třídící algoritmy =====+===== Řadicí algoritmy =====
  
 ==== Bubble sort ==== ==== Bubble sort ====
  
 **Princip:** **Princip:**
-  - Dostanu zadané pole. +  - Dostanu pole. 
-  - Procházím pole, pokud je prvek vlevo menší než prvek vpravo prohodím je +  - Procházím pole, pokud najdu prvek, který je menší než prvek vpravo, prohodím je. 
-  - Opakuji dokud není pole seřazeno od největšího po nejmenší (zprava doleva)+  - Opakuji, dokud není pole seřazeno od největšího po nejmenší (zprava doleva).
  
-**Složitost:** O(n<sup>2</sup>) -> za každý prvek pole projdu pole dvakrát+**Složitost:** O(n<sup>2</sup>)
  
 **Ukázka algoritmu:** **Ukázka algoritmu:**
Řádek 88: Řádek 89:
  
 **Princip:** **Princip:**
-  - Dostanu pole +  - Dostanu pole. 
-  - Procházím pole zleva doprava a vždy každý prvek zařadím na místo podle velikosti +  - Procházím pole zleva doprava a vždy každý prvek zařadím na místo podle jeho velikosti. 
-  - Dostávám pole seřazené zleva doprava od největšího po nejmenší+  - Dostávám pole seřazené zleva doprava (od největšího po nejmenší).
  
-**Složitost:** Složitost je O(n<sup>2</sup>), ale při téměř seřazeném poli se blíží O(n)+**Složitost:** Složitost je O(n<sup>2</sup>), ale při téměř seřazeném poli se blíží O(n).
  
 **Ukázka algoritmu:** **Ukázka algoritmu:**
Řádek 156: Řádek 157:
  
 ==== Merge sort ==== ==== Merge sort ====
 +https://www.algoritmy.net/article/13/Merge-sort
 +
 **Princip:** **Princip:**
-  - Dostaneme pole +  - Dostaneme pole. 
-  - Toto pole si rozdělíme na dvě podpole +  - Pole rozdělíme na dvě zhruba stejně velká podpole. 
-  - Dokud není pole rozděleno na jednoprvkové pole opakuj krok č.2 +  - Získané podpole dále dělíme až na jednoprvkové pole (získáme n jednoprvkových polí). 
-  - Jakmile máme jednoprvková pole spojíme je dohromady tak, aby byly seřazeny  +  - Jakmile máme jednoprvková pole spojujeme je dohromady tak, aby byly seřazeny. 
-  - Jakmile máme jenom dvě podmnožiny porovnáme vždy jednotlivé prvky množiny a vždy ten větší přidáme do finálního pole --> postupujeme až máme ve finálním poli prvky od největšího po nejmenší+  - Jakmile máme jenom dvě podmnožiny, porovnáme vždy jednotlivé prvky množiny a vždy ten větší přidáme do finálního pole -> postupujeme až máme ve finálním poli prvky od největšího po nejmenší.
  
-**Složitost:** Složitost algoritmu O(n * log(n))+**Složitost:** O(n * log(n))
  
-Protože to nejsem schopný naprogramovat ukázku máte [[https://www.youtube.com/watch?v=EeQ8pwjQxTM|zde]] :-(.+Ukázka [[https://www.youtube.com/watch?v=EeQ8pwjQxTM|zde]].
  
 ==== Quick sort ==== ==== Quick sort ====
 **Princip:** **Princip:**
-  - Dostaneme pole +  - Dostaneme pole. 
-  - Zvolíme si jeden prvek pole (pivot) a rozdělíme zbytek pole na prvky větší než pivot a na prvky menší než pivot +  - Zvolíme si jeden prvek pole (pivot) a rozdělíme zbytek pole na prvky větší než pivot a na prvky menší než pivot (stejně velké prvky mohou být na libovolné straně). 
-  - Pivota umístíme mezi tyto dvě množiny -> pivot je na místě, kam by patřil v seřazeném poli +  - Pivota umístíme mezi tyto dvě množiny (pivot je na místě, kam by patřil v seřazeném poli). 
-  - Kroky opakujeme, dokud nemáme všechny prvky seřazeny+  - Kroky opakujeme, dokud nemáme všechny prvky seřazeny.
  
-**Složitost:** Složitost u quick sortu je hodně závislá na volbě pivota(resp. pivotů). Pokud je pivot mediánem hodnot může být složitost O(n * log(n)), pokud však je pivot největším nebo nejmenším prvkem pole je složitost O(n<sup>2</sup>). Pivota můžeme vybrat, jako fixní pozici v tabulce (např. vždy poslední nebo první nebo prostřední prvek) nebo, což se považuje za idealnější případ, se vyberou tři hodnoty a z nich se udělá medián.+**Složitost:** Složitost u quick sortu je hodně závislá na volbě pivota (resp. pivotů). Pokud je pivot mediánem hodnot, může být složitost až O(n * log(n)), pokud je však pivot největším nebo nejmenším prvkem pole je složitost O(n<sup>2</sup>). Pivota můžeme vybrat jako fixní pozici v tabulce (např. vždy poslední, první nebo prostřední prvek) nebo, což se považuje za ideální případ, se vyberou tři hodnoty pole, ze kterých se udělá medián.
  
-Protože to nejsem schopný naprogramovat ukázku máte [[http://www.algoritmy.net/article/10/Quicksort|zde]] :-(.+Ukázka [[http://www.algoritmy.net/article/10/Quicksort|zde]].
  
  
 ==== Selection sort ==== ==== Selection sort ====
 **Princip:** **Princip:**
-  - Dostaneme pole +  - Dostaneme pole. 
-  - Vyhledáme největší prvek pole a umístíme ho doleva +  - Vyhledáme největší prvek pole a umístíme ho doleva. 
-  - Toto opakujeme, dokud nemáme seřazeno+  - Toto opakujeme, dokud nemáme seřazeno.
  
-**Složitost:** Složitost je sice u selection sortu vysoká O(n<sup>2</sup>), ale dobrá je u něj jeho nízká paměťová náročnost+**Složitost:** Složitost je sice u selection sortu vysoká O(n<sup>2</sup>), ale má velmi nízkou paměťovou náročnost.
  
 [[http://www.algoritmy.net/article/4/Selection-sort|Ukázka algoritmu]] [[http://www.algoritmy.net/article/4/Selection-sort|Ukázka algoritmu]]
Řádek 191: Řádek 194:
 ===== Vyhledávací algoritmy ===== ===== Vyhledávací algoritmy =====
  
-==== Lineární hledání (také sekvenční hledání) ==== +==== Lineární hledání (sekvenční hledání) ==== 
-**Princip:** Procházím všechny prvky, dokud nenajdu ten hledaný.+**Princip:** Procházíme všechny prvky, dokud nenajdu ten hledaný.
  
 **Složitost:** O(n) **Složitost:** O(n)
  
-==== Binární hledání (též metoda půlení intervalů) ====+==== Binární hledání (metoda půlení intervalů) ====
 **Princip:**  **Princip:** 
-  - Pole ve kterém se dá použít půlení intervalů musí být seřazeno (v tomto případě od největšího po nejmenší) +  - Pole ve kterém se dá použít půlení intervalů, musí být seřazeno (v tomto případě od největšího po nejmenší). 
-  - Podívám se na prostřední prvek pole +  - Podívám se na prostřední prvek pole. 
-  - Pokud je můj hledaný prvek větší opakuji to stejné vpravo, pokud menší tak vlevo +  - Pokud je můj hledaný prvek větší opakuji to stejné vpravo, pokud menší tak vlevo. 
-  - Opakuji dokud nenajdu hledané číslo+  - Opakuji, dokud nenajdu hledaný prvek.
  
 **Složitost:** O(log<sub>2</sub>(n)) **Složitost:** O(log<sub>2</sub>(n))
Řádek 207: Řádek 210:
 ==== Metoda binárního vyhledávacího stromu ==== ==== Metoda binárního vyhledávacího stromu ====
  
-**Princip:** Tvořím binární strom (viz. obrázek) tak, že vždy v levé větvi jsou menší prvky a v pravé jsou větší prvky. Hledaný prvek hledáme tak, že za ním jdeme po větvi.+**Princip:** Tvořím binární strom (viz obrázek) tak, že vždy v levé větvi jsou menší prvky a v pravé jsou větší prvky. Hledaný prvek hledáme tak, že za ním jdeme po větvi.
  
 {{:informatika:maturita:22_binarni_strom.jpg|}} {{:informatika:maturita:22_binarni_strom.jpg|}}
  
-**Složitost:** V závislosti na vyvážení stromu (= vyvážený počet větví obou stranách) může být buď O(log(n)) pro vyážený strom nebo O(n) pro nevyvážený. +**Složitost:** V závislosti na vyvážení stromu (podle vyváženého počtu větví na obou stranách) může být buď O(log(n)) pro naprosto vyvážený strom, nebo až O(n) pro vůbec nevyvážený strom.
- +
- +
- +
informatika/maturita/22a.1429882660.txt.gz · Poslední úprava: autor: xmrnustik
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki