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²)
2. BO(n log n)
3. CO(n + k)
4. DO(k log n)

Ką reiškia, jei operacija atliekama per O(1) laiką?

1. AJi apdoroja lygiai vieną elementą per vykdymo sekundę
2. BJos vykdymo laikas nedidėja didėjant įvesties dydžiui
3. CJą galima vykdyti tik vieną kartą
4. DJi visada trunka lygiai vieną sekundę

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

Godusis algoritmas:

1. AIšbando kiekvieną galimą sprendinį
2. BNaudoja tik rekursiją
3. CVisada pateikia optimalų sprendinį
4. DKiekviename žingsnyje priima lokaliai geriausią sprendimą

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Kodėl dinaminis programavimas realiai nepagreitina rikiavimo suliejimu?

1. ADinaminis programavimas veikia tik su grafų uždaviniais, bet ne su masyvais
2. BRikiavimas suliejimu neturi rekursinės struktūros
3. CRikiavimas suliejimu jau yra O(n)
4. DJo daliniai uždaviniai nepersidengia, todėl nėra ko pakartotinai panaudoti

Kuris teiginys apie P ir NP yra teisingas?

1. AĮrodyta, kad P ≠ NP
2. BNP uždavinių sprendinių negalima greitai patikrinti
3. CNP reiškia „nepolinominis“ (not polynomial)
4. DKiekvienas P klasės uždavinys taip pat priklauso NP

Kuris iš šių įvykdomumo uždavinių, kaip žinoma, išsprendžiamas per polinominį laiką?

1. ALoginės schemos įvykdomumas
2. B2-SAT, kai kiekviename disjunkte yra daugiausia du literalai
3. CBendrasis SAT konjunkcinės normaliosios formos formulėms
4. D3-SAT, kai kiekviename disjunkte yra lygiai trys literalai