Kartičky na Dynamické dátové štruktúry a algoritmy
Dynamické Dátové Štruktúry a Algoritmy: Komplexný Sprievodca
Ťukni na otočenie · Potiahni na navigáciu
Dátové štruktúry - lineárne a triedenie
42 kartičiek
Kartička 1
Otázka: Čo sú dynamické dátové štruktúry a kedy sa používajú?
Odpoveď: Dátové štruktúry, ktorých veľkosť sa môže počas behu programu meniť; umožňujú pridávať, odoberať alebo prepájať prvky a používajú sa, keď nepoznáme do
Kartička 2
Otázka: Ako označujeme čas behu algoritmu a čo nás pri ňom zaujíma?
Odpoveď: Čas behu označujeme T(n), kde n je veľkosť vstupu; zaujíma nás hlavne, ako sa čas mení pri zväčšovaní vstupu (asymptotická zložitosť).
Kartička 3
Otázka: Ktorú notáciu najčastejšie používame pre asymptotickú zložitosť a čo vyjadruje?
Odpoveď: Používame notáciu O, ktorá vyjadruje horný odhad rastu času behu pri zväčšovaní vstupu.
Kartička 4
Otázka: Uveďte príklady typických časových zložitostí.
Odpoveď: O(1), O(log n), O(n), O(n log n), O(n²).
Kartička 5
Otázka: Aké sú tri prípady časovej zložitosti, ktoré rozlišujeme?
Odpoveď: Najlepší prípad (best-case), priemerný prípad (average-case), najhorší prípad (worst-case).
Kartička 6
Otázka: Čo hovorí pamäťová zložitosť a aké sú typické kategórie?
Odpoveď: Udáva množstvo dodatočnej pamäte potrebnej algoritmom; in-place algoritmy (O(1) alebo O(log n)) a externé algoritmy (O(n)).
Kartička 7
Otázka: Ako funguje merge sort a aký je jeho rekurentný vzťah?
Odpoveď: Divide and conquer: rozdelí pole na dve polovice, rekurzívne ich utriedi a spojí; rekurentný vzťah T(n)=2T(n/2)+O(n).
Kartička 8
Otázka: Aká je asymptotická časová zložitosť merge sortu a jeho prípadné varianty (best/avg/worst)?
Odpoveď: T(n)=O(n log n); best-case, average-case a worst-case sú všetky O(n log n).
Kartička 9
Otázka: Aké sú hlavné vlastnosti merge sortu?
Odpoveď: Stabilný algoritmus, vyžaduje dodatočnú pamäť O(n), vhodný pre veľké dáta a externé triedenie.
Kartička 10
Otázka: Ako funguje quick sort a aké rekurentné vzťahy popisujú priemerný a najhorší prípad?
Odpoveď: Vyberie pivot, rozdelí prvky na menšie a väčšie ako pivot a rekurzívne ich triedi; priemer: T(n)=2T(n/2)+O(n), najhorší: T(n)=T(n−1)+O(n).