Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : Vnitřní Třídění
Přihlášení:  Heslo:  
Matfiz: VnitřníTřídění ...
Hlavní Stránka | Seznam Stránek | Poslední Změny | Poslední Komentované | Uživatelé | Registrace |

Vnitřní třídění


Vnitřní třídění je (oproti vnějšímu) třídění prvků pole v operační paměti, nikoli v souboru.


Různé algoritmy pro třídění dle přednášky 5. ledna 2006:


Složitost úlohy

Tvrzení: Úloha vnitřního třídění založeného na porovnávání dvou prvků má (časovou) složitost n log n.


Důkaz: Větší určitě nemá (viz Heap Sort). Mějme strom výpočtu (strom všech provedených operací), který se podle pořadí daných dat větví při porovnáních. Takový strom má n! listů, výška je tedy aspoň log(n!) a to se dá odhadnout (prý) jako n log n.


 
Soubory [Skrýt soubory (formulář)]
Na stránce nejsou žádné komentáře. [Zobrazit komentáře (formulář)]