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

Algoritmo vykdymo laikas yra O(n). Kaip vadinamas toks augimas?

1. ALogaritminis
2. BKvadratinis
3. CTiesinis
4. DPastovus

Prieiga prie masyvo elemento pagal indeksą užtrunka:

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

Kas yra rekursinės funkcijos bazinis atvejis?

1. AKvietimas, naudojantis daugiausia atminties
2. BAtvejis, į kurį atsakoma tiesiogiai, neatliekant kito rekursinio kvietimo
3. CPirmoji funkcijos eilutė
4. DAtvejis su didžiausia įvestimi, kuris apdorojamas prieš bet kokius rekursinius kvietimus

Kodėl daug bibliotekinių rikiavimo procedūrų labai mažiems daliniams masyvams pereina prie rikiavimo įterpimu?

1. ARekursiniai algoritmai negali apdoroti mažesnių nei 10 elementų masyvų
2. BRikiavimas įterpimu blogiausiu atveju yra O(n log n)
3. CRikiavimas įterpimu didelėms įvestims naudoja mažiau atminties nei bet kuris kitas rikiavimo algoritmas
4. DRikiavimas įterpimu turi mažas pridėtines sąnaudas ir yra greitas su mažomis ar beveik surikiuotomis įvestimis

Godusis algoritmas:

1. ANaudoja tik rekursiją
2. BIšbando kiekvieną galimą sprendinį
3. CKiekviename žingsnyje priima lokaliai geriausią sprendimą
4. DVisada pateikia optimalų sprendinį

Ar teisinga sakyti, kad O(n²) algoritmas yra ir O(n³)?

1. ANe, nes didysis O visada turi nurodyti tikslų funkcijos augimo greitį
2. BNe, nes dideliems n n³ mažesnis už n²
3. CTaip, bet tik jei n mažesnis už 100
4. DTaip, nes didysis O yra viršutinis rėžis, o n² auga ne greičiau už n³

Heldo–Karpo dinaminio programavimo algoritmas tiksliai išsprendžia keliaujančio pirklio uždavinį. Koks jo vykdymo laikas n miestų?

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)

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²)