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

Kokie yra trys „skaldyk ir valdyk“ algoritmo žingsniai?

1. ASkaityk, skaičiuok, rašyk
2. BSurikiuok, ieškok, grąžink
3. CPadalyk, išspręsk, sujunk
4. DSpėk, tikrink, kartok

Kokį sudėtingumą paprastai turi algoritmas su dviem įdėtiniais ciklais, kurių kiekvienas vykdomas n kartų?

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

Kas yra memoizacija?

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

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

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

Kodėl didžiojo O žymėjime logaritmo pagrindas paprastai nenurodomas, kaip O(log n)?

1. APagrindas svarbus tik mažiems n
2. BSkirtingų pagrindų logaritmai skiriasi tik pastoviu daugikliu
3. CLogaritmai visada apvalinami iki sveikųjų skaičių
4. DVisų logaritmų informatikoje pagrindas yra 10, todėl jis numanomas

Greitasis rikiavimas visada kaip atraminį elementą naudoja pirmąjį elementą. Su kokia įvestimi jis elgiasi blogiausiai?

1. ASu jau surikiuotu masyvu
2. BSu 2 ilgio masyvu
3. CSu masyvu, kurio visi elementai skirtingi
4. DSu atsitiktinės tvarkos masyvu

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

Kodėl bet kuriai palyginimais pagrįstai paieškai surikiuotame masyve blogiausiu atveju reikia Ω(log n) palyginimų?

1. ADvejetainė paieška yra vienintelis galimas algoritmas, ir jam reikia log₂ n palyginimų
2. BSprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
3. CKiekvieną elementą reikia palyginti bent kartą
4. DKiekvienas palyginimas trunka logaritminį laiką