08-Trideni_uvod
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.
• Průměrný počet přesunů v průběžném kroku:
0+𝑘
2
=
𝑘
2
• Maximální počet přesunů v průběžném kroku: 𝑘
Složitost algoritmu třídění přímým vkládáním
• Průměrný počet přesunů pro celé třídění:
1 + 2 + ⋯ + 𝑛 − 1
2
=
𝑛 − 1 1 + 𝑛 − 1
2
2
=
𝑛2 − 𝑛
4
• Maximální počet přesunů pro celé třídění:
1 + 2 + ⋯ + 𝑛 − 1 =
𝑛 − 1 1 + 𝑛 − 1
2
=
𝑛2 − 𝑛
2
• Operace přesunů má kvadratickou složitost bez ohledu na to, zda
bereme průměrnou nebo maximální hodnotu možných přesunů.
Složitost algoritmu třídění přímým vkládáním
• Při více operacích se výsledná míra složitosti odvozuje od operace s
největší složitostí.
• Zde obě operace (srovnání, přesun) mají stejnou - kvadratickou míru
složitosti.
• Výsledná míra složitosti je tedy kvadratická.