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

Ko dvejetainė paieška reikalauja iš savo įvesties?

1. AMasyve turi būti ne daugiau kaip 1000 elementų
2. BMasyve turi būti tik teigiami skaičiai
3. CMasyvas turi būti surikiuotas
4. DMasyvo ilgis turi būti dvejeto laipsnis

Kas yra perrinkimo (brute force) algoritmas?

1. AAlgoritmas, kuris visada naudoja rekursiją
2. BAlgoritmas, atsitiktinai spėjantis atsakymą
3. CAlgoritmas, išbandantis visus galimus kandidatinius sprendinius
4. DAlgoritmas, veikiantis daugelyje procesorių

Kas yra memoizacija?

1. AAtminties atlaisvinimas funkcijai grįžus
2. BAutomatinis rekursijos pavertimas ekvivalenčiu ciklu, kad nebereikėtų kvietimų steko
3. CFunkcijų kvietimų rezultatų saugojimas, kad į pakartotinius kvietimus būtų atsakoma iš atminties
4. DKomentarų rašymas prie kiekvienos kodo eilutės

Kuris rikiavimo algoritmas yra stabilus?

1. ARikiavimas krūva
2. BGreitasis rikiavimas (įprasta versija vietoje)
3. CRikiavimas išrinkimu (įprasta versija)
4. DRikiavimas suliejimu

Ką reiškia, kad uždavinys turi optimalią struktūrą (optimal substructure)?

1. AVisi daliniai uždaviniai yra vienodo dydžio
2. BUždavinį galima išspręsti per pastovų laiką
3. COptimalų sprendinį galima sudaryti iš optimalių jo dalinių uždavinių sprendinių
4. DUždavinys turi lygiai vieną optimalų sprendinį, kurį bendrai turi visi dalinių uždavinių sprendiniai

Ką apskaičiuoja Floydo–Warshallo algoritmas ir kaip greitai?

1. AMinimalų jungiamąjį medį per O(E log V)
2. BTrumpiausius kelius tarp visų viršūnių porų per O(V³)
3. CTopologinę tvarką per O(V²)
4. DTrumpiausius kelius iš vienos šaltinio viršūnės į visas kitas per O(V + E)

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

Koks yra dvejetainės krūvos sudarymo iš n nesurikiuotų elementų metodu „iš apačios į viršų“ (bottom-up) laiko sudėtingumas?

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