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

Erdvės (atminties) sudėtingumas matuoja:

1. AProgramos failo užimamą vietą diske jį sukompiliavus
2. BKiek atminties algoritmui reikia didėjant įvesties duomenims
3. CKodo eilučių skaičių
4. DFizinį kompiuterio dydį

Ką reiškia f(n) = Θ(g(n))?

1. Af auga tokiu pat greičiu kaip g, iš viršaus ir apačios apribota pastoviais g kartotiniais
2. Bf visada mažesnė už g su kiekvienu n, todėl g riboja ją iš viršaus, bet niekada iš apačios
3. Cf auga griežtai greičiau už g
4. Df auga griežtai lėčiau už g

O(n²) algoritmas, kai n = 1000, trunka 1 sekundę. Maždaug kiek jis truks, kai n = 2000?

1. A2 sekundes
2. B4 sekundes
3. C1 sekundę
4. D8 sekundes

Turint 1, 3 ir 4 vertės monetas ir 6 sumą, kiek monetų panaudoja godusis metodas „pirmiausia didžiausia moneta“, palyginti su optimaliu sprendiniu?

1. AGodusis panaudoja 4 monetas; optimalus sprendinys – 3
2. BGodusis panaudoja 2 monetas; optimalus sprendinys – 2
3. CGodusis panaudoja 3 monetas; optimalus sprendinys – 3
4. DGodusis panaudoja 3 monetas; optimalus sprendinys – 2

Palyginimais pagrįsto rikiavimo apatinis rėžis blogiausiu atveju yra:

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

Koks yra amortizuotas laiko sudėtingumas pridedant elementą į dinaminio masyvo, kuris prisipildęs padvigubina savo talpą, galą?

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

Kaip klasifikuojamas keliaujančio pirklio uždavinys?

1. ASprendimo versija yra NP-pilna, o optimizavimo versija – NP-sunki
2. BJis neišsprendžiamas
3. CSprendimo versija priklauso P, bet optimizavimo versija yra NP-pilna
4. DJis priklauso P, nes jį išsprendžia Dijkstros algoritmas aplankydamas kiekvieną miestą vieną kartą

Koks yra šio kodo laiko sudėtingumas: for i = 1 to n: for (j = i; j ≤ n; j = j + i) atlikti O(1) darbą?

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