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

Koks yra rikiavimo skaičiavimu vykdymo laikas n sveikųjų skaičių intervale nuo 0 iki k?

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

Kuris rikiavimo algoritmas pasirenka atraminį elementą ir padalija masyvą į mažesnius ir didesnius elementus?

1. ARikiavimas suliejimu
2. BBurbuliuko rikiavimas
3. CRikiavimas įterpimu
4. DGreitasis rikiavimas (quicksort)

Koks yra rikiavimo įterpimu laiko sudėtingumas geriausiu atveju, kai masyvas jau surikiuotas?

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

Kam lygus rekurentinės lygties T(n) = 2T(n − 1) + O(1) sprendinys?

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

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

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

Koks yra n-tojo Fibonačio skaičiaus skaičiavimo laiko sudėtingumas, naudojant lentelę „iš apačios į viršų“?

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

Kuris metodas užtikrina tikėtiną O(n log n) greitojo rikiavimo vykdymo laiką bet kokiems įvesties duomenims?

1. AĮvesties duomenų surikiavimas prieš paleidžiant greitąjį rikiavimą
2. BRekursijos taikymas tik kairiajai pusei
3. CVisada pirmojo elemento parinkimas
4. DAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį

Uždavinys yra NP-pilnas, jei jis:

1. APriklauso NP ir kiekvienas NP uždavinys į jį redukuojamas per polinominį laiką
2. BNepriklauso NP, bet yra sunkesnis už visus NP uždavinius, pvz., sustojimo problema
3. CIšsprendžiamas per polinominį laiką
4. DNeišsprendžiamas