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

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

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

Ką apibūdina vykdymo laikas vidutiniu atveju?

1. ALaiką vidutinio ilgio įvesčiai
2. BVidurinę reikšmę tarp geriausio ir blogiausio atvejo vykdymo laikų
3. CLaiką labiausiai paplitusiame kompiuteryje
4. DTikėtiną laiką esant tam tikram n dydžio įvesčių skirstiniui

Koks yra tiesinės paieškos nesurikiuotame n elementų masyve laiko sudėtingumas (blogiausiu atveju)?

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

Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?

1. APasirinkti anksčiausiai prasidedančią veiklą
2. BPirmiausia pasirinkti trumpiausią veiklą
3. CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
4. DPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis

Maždaug kiek palyginimų blogiausiu atveju reikia dvejetainei paieškai surikiuotame 1,000,000 elementų masyve?

1. AApie 500,000
2. BApie 1,000
3. CApie 100
4. DApie 20

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

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

Strasseno algoritmas matricas daugina naudodamas 7, o ne 8 rekursines pusės dydžio blokų daugybas. Koks jo vykdymo laikas?

1. AΘ(n²)
2. BΘ(n² log n)
3. CΘ(n³)
4. DΘ(n^{log₂ 7}), apie n^2,81

Kas išplauktų, jei kas nors rastų polinominio laiko algoritmą vienam NP-pilnam uždaviniui?

1. AVisi eksponentinio laiko algoritmai nedelsiant imtų veikti tiesiniu laiku
2. BKiekvieną NP uždavinį būtų galima išspręsti per polinominį laiką, taigi P = NP
3. CStabdymo problema taptų išsprendžiama
4. DTik tas vienas uždavinys pereitų į P