ptans 1 Flashcards
(26 cards)
Co jsou datové struktury s dynamickým přidělováním paměti?
Dynamicky rostoucí pole, lineární seznam, hash tabulka, binární strom
Tyto struktury se vyznačují tím, že se jejich velikost může během provádění programu měnit.
Jaký je rozdíl mezi časovou a prostorovou složitostí?
Časová složitost = jak dlouho algoritmus poběží v závislosti na velikosti vstupních dat; Prostorová složitost = kolik paměti je potřeba k vykonání algoritmu v závislosti na velikosti vstupních dat
Obě složitosti jsou klíčové pro analýzu efektivity algoritmů.
Co znamená asymptotická složitost?
Udává funkci, jak bude narůstat výpočetní složitost v závislosti na velikosti vstupních dat
Asymptotická složitost se často vyjadřuje pomocí Big O Notation.
Co vyjadřuje časová složitost O(n)?
Doba trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu
O(n) představuje lineární časovou složitost.
Co znamená složitost O(n^2)?
Doba trvání průběhu se zvyšuje kvadraticky, pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší čtyřikrát
O(n^2) je typická pro primitivní třídící algoritmy.
Jaké jsou základní asymptotické třídy?
- Θ(1) = konstantní
- Θ(log n) = logaritmický růst
- Θ(n*log n) = chytré sort algoritmy
- Θ(n) = lineární růst
- Θ(n^2) = kvadratický růst
- Θ(n^3) = kubický růst
- Θ(n^k) = polynomiální růst
- Θ(n!) = faktoriální růst
Tyto třídy pomáhají kategorizovat různé algoritmy podle jejich složitosti.
Jak funguje dynamicky rostoucí pole?
Umožňuje přidávat libovolný počet prvků; při vyčerpání kapacity alokuje větší pole a kopíruje prvky
Chování se opakuje, když je pole příliš prázdné.
Jaká je časová složitost vkládání prvku do dynamického pole?
Θ(n)
Vkládání je nákladné, pokud je potřeba alokovat nové pole.
Jaká je časová složitost vyhledání jednoho prvku v dynamickém poli?
Θ(1)
Vyhledání je efektivní, protože se provádí pomocí indexu.
Jaká je časová složitost smazání jednoho prvku v dynamickém poli?
Závisí na implementaci: Θ(1) nebo Θ(n)
Záleží na tom, zda se prvky přesouvají nebo se pouze mění místo.
Jaká metoda se používá pro rychlé řazení prvků v dynamickém poli?
Quick sort
Quick sort je efektivní třídící algoritmus.
Jaký je princip lineárního seznamu?
Všechny prvky mají ukazatel na následující položku, nemusí být v paměti lineárně uspořádány
Může být jednosměrný nebo obousměrný.
Jaká je časová složitost vkládání prvku do lineárního seznamu?
Θ(1) na začátku a konci, Θ(n) doprostřed
Vkládání na začátek nebo konec je rychlé, ale uprostřed vyžaduje vyhledání.
Jaká je časová složitost vyhledání jednoho prvku v lineárním seznamu?
Θ(n)
Vyhledání vyžaduje procházení seznamu.
Jaká je časová složitost smazání jednoho prvku v lineárním seznamu?
Θ(n) + Θ(1)
Zahrnuje vyhledání a samotné mazání.
Jaká metoda se používá pro rychlé řazení prvků v lineárním seznamu?
Merge sort
Merge sort je efektivní třídící algoritmus pro seznamy.
Co je hash tabulka?
Vyhledávací datová struktura typu key-value, kombinuje výhody indexovaného vyhledávání a lineárního seznamu
Používá hašovací funkci pro přiřazení klíče k indexu.
Jaká je časová složitost vkládání prvku do hash tabulky?
Průměrně Θ(1), v nejhorším případě Θ(n)
V nejhorším případě může dojít ke kolizím.
Jaká je časová složitost vyhledání jednoho prvku v hash tabulce?
Průměrně Θ(1), v nejhorším případě Θ(n)
Vyhledání je rychlé díky indexaci.
Jaká je časová složitost smazání jednoho prvku v hash tabulce?
Průměrně Θ(1), v nejhorším případě Θ(n)
Podobně jako u vyhledání, smazání může být ovlivněno kolizemi.
Jaká metoda se používá pro rychlé řazení prvků v hash tabulce?
Nelze ji řadit, pořadí určuje hash funkce
Pro seřazenou tabulku lze použít SortedDictionary.
Jaký je princip binárního stromu?
Každý prvek má nejvíc jednoho předchůdce a může mít více následníků; levý podstrom obsahuje menší prvky, pravý větší
Binární stromy jsou často používané v informatice.
Jaká je časová složitost vkládání prvku do binárního stromu?
Průměrně Θ(log n), v nejhorším případě Θ(n)
V nejhorším případě může být strom nevyvážený.
Jaká je časová složitost vyhledání jednoho prvku v binárním stromu?
Průměrně Θ(log n), v nejhorším případě Θ(n)
Vyhledání je efektivní v dobře vyvážených stromech.
