Test na Srovnání řadicích algoritmů a časová složitost
Srovnání řadicích algoritmů a časová složitost pro studenty
Test: Řadicí algoritmy a jejich vlastnosti
20 otázek
Otázka 1: In-place řadicí algoritmy mají často paměťovou složitost O(1) nebo O(log n pro rekurzivní volání.
A. Ano
B. Ne
Vysvětlení: Podle studijních materiálů jsou in-place algoritmy definovány jako ty, které pracují přímo s původními daty a nepotřebují mnoho dodatečné paměti. Dále je uvedeno, že 'Jejich paměťová složitost je často O(1) nebo O(log n) pro rekurzivní volání'.
Otázka 2: Při srovnávání řadicích algoritmů se mezi klíčové metriky řadí časová složitost, paměťová složitost a stabilita.
A. Ano
B. Ne
Vysvětlení: Studijní materiály explicitně uvádějí časovou složitost, paměťovou složitost a stabilitu jako klíčové metriky pro srovnávání řadicích algoritmů v sekci 'Základní pojmy a kritéria srovnání'.
Otázka 3: Bubble Sort a Quick Sort jsou typickými příklady algoritmů, které vyžadují významné množství dodatečné paměti pro své fungování, a proto nejsou považovány za 'in-place'.
A. Ano
B. Ne
Vysvětlení: Podle studijních materiálů se algoritmy, které pracují přímo s původními daty a nepotřebují mnoho dodatečné paměti, nazývají 'in-place' algoritmy. Bubble Sort a Quick Sort jsou explicitně uvedeny jako příklady těchto 'in-place' algoritmů, což znamená, že nepotřebují významné množství dodatečné paměti.
Otázka 4: Výkon řadicích algoritmů není nikdy ovlivněn charakterem vstupních dat, jako je jejich částečné seřazení nebo náhodnost.
A. Ano
B. Ne
Vysvětlení: Studijní materiály uvádějí, že výkon některých algoritmů je výrazně ovlivněn charakterem vstupních dat, například tím, zda jsou data již částečně seřazena, seřazena v opačném pořadí, nebo zcela náhodná. Tvrzení, že výkon není nikdy ovlivněn, je tedy nepravdivé.
Otázka 5: Všechny řadicí algoritmy, které porovnávají sousední prvky, mají časovou složitost O(n²).
A. Ano
B. Ne
Vysvětlení: Studijní materiály uvádějí, že Bubble Sort porovnává sousední prvky a má časovou složitost O(n²). Nicméně, materiály nezmiňují, že by to platilo pro VŠECHNY algoritmy porovnávající sousední prvky. Také není vyloučeno, že by jiný algoritmus s lepší časovou složitostí mohl používat srovnávání sousedních prvků, byť to není explicitně popsáno.