Užduočių lapas tema Algoritmai ir sudėtingumas su atsakymais

Koks yra rikiavimo suliejimu laiko sudėtingumas blogiausiu atveju?

1. AO(n²)
2. BO(n log n)
3. CO(n)
4. DO(log n)

Kurią projektavimo strategiją naudoja rikiavimas suliejimu?

1. ASkaldyk ir valdyk
2. BDinaminį programavimą
3. CPerrinkimą (brute force)
4. DGodųjį pasirinkimą

Kiek papildomos atminties naudoja standartinis masyvu grįstas rikiavimas suliejimu?

1. AO(log n)
2. BO(n²)
3. CO(1)
4. DO(n)

Kiek lygmenų turi rikiavimo suliejimu rekursija n elementų masyvui?

1. AApie log₂ n
2. BApie √n
3. CApie n
4. DApie n / 2

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

1. ARikiavimas įterpimu blogiausiu atveju yra O(n log n)
2. BRikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
3. CRekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
4. DRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis

Kaip Primo algoritmas sudaro minimalų jungiamąjį medį?

1. AJis augina vieną medį nuo pradinės viršūnės, kaskart pridėdamas pigiausią iš medžio išeinančią briauną
2. BJis surikiuoja visas briaunas pagal svorį ir prideda kiekvieną, jei ji miške nesudaro ciklo
3. CJis vykdo paiešką platyn ir pasilieka BFS medį
4. DJis šalina brangiausią briauną, kol nebelieka ciklų

Kam lygus rekurentinės lygties T(n) = 2T(n/2) + n log n sprendinys?

1. AΘ(n log² n)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n)

Trumpiausius paprastuosius kelius galima rasti per polinominį laiką. Kas žinoma apie ilgiausio paprastojo kelio tarp dviejų viršūnių paiešką bendrajame grafe?

1. AJį galima išspręsti Dijkstros algoritmu su priešingo ženklo svoriais
2. BTai NP-sunkus uždavinys
3. CJis neišsprendžiamas
4. DJis visada išsprendžiamas per O(V + E)