Kartičky na Triedenie zlučovaním (merge sort)
Triedenie zlučovaním (Merge Sort): Kompletný Rozbor pre študentov
Ťukni na otočenie · Potiahni na navigáciu
Triedenie zlučovaním (Merge Sort)
23 kartičiek
Kartička 1
Otázka: Aká je časová zložitosť algoritmu Merge Sort?
Odpoveď: Časová zložitosť algoritmu Merge Sort je O(n log n) pre všetky prípady: najlepší, priemerný aj najhorší.
Kartička 2
Otázka: Prečo je časová zložitosť Merge Sort O(n log n)?
Odpoveď: Časová zložitosť je O(n log n), pretože proces rozdeľovania poľa prebieha log n krát a na každej z týchto log n úrovní rekurzie sa vykonáva operácia z
Kartička 3
Otázka: Aká je pamäťová náročnosť (Space Complexity) Merge Sort?
Odpoveď: Pamäťová náročnosť Merge Sort je O(n), pretože vyžaduje dodatočný pamäťový priestor pre dočasné polia počas fázy zlučovania, ktorý je úmerný počtu prv
Kartička 4
Otázka: Je Merge Sort in-place algoritmus?
Odpoveď: Nie, štandardná implementácia Merge Sort nie je in-place algoritmus, pretože vyžaduje O(n) dodatočného pamäťového priestoru. Hoci existujú zložitejšie
Kartička 5
Otázka: Je Merge Sort vždy najrýchlejší pre všetky veľkosti vstupov, napriek jeho O(n log n) zložitosti?
Odpoveď: Nie, pre veľmi malé polia môžu byť jednoduchšie algoritmy (ako napríklad Insertion Sort) rýchlejšie vďaka menšej konštantnej réžii.
Kartička 6
Otázka: Je časová zložitosť Merge Sort ovplyvnená počiatočným usporiadaním dát (napr. opačne triedeným poľom)?
Odpoveď: Nie, Merge Sort je stabilný voči počiatočnému usporiadaniu dát, takže jeho časová zložitosť zostáva O(n log n) aj pre opačne triedené pole.
Kartička 7
Otázka: Prečo je O(n log n) považovaná za optimálnu zložitosť pre porovnávacie triediace algoritmy?
Odpoveď: Žiadny porovnávací triediaci algoritmus nemôže byť asymptoticky rýchlejší ako O(n log n).
Kartička 8
Otázka: Čo je Triedenie zlučovaním (Merge Sort)?
Odpoveď: Jeden z najefektívnejších a najčastejšie používaných triediacich algoritmov v informatike, patriaci do kategórie porovnávacích triediacich algoritmov,
Kartička 9
Otázka: Kto vynašiel Triedenie zlučovaním a kedy?
Odpoveď: John von Neumann v roku 1945.
Kartička 10
Otázka: Aká je hlavná výhoda Merge Sortu?
Odpoveď: Stabilná výkonnosť bez ohľadu na počiatočné usporiadanie vstupných dát, čo z neho robí spoľahlivú voľbu pre triedenie veľkých dátových súborov.