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

Kuris iš šių auga lėčiausiai, kai n tampa didelis?

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

Koks yra rikiavimo įterpimu laiko sudėtingumas blogiausiu atveju?

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

Kas yra memoizacija?

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

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

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

Funkcija vykdo vieną n iteracijų ciklą, o paskui, atskirai, dar vieną n iteracijų ciklą. Koks jos laiko sudėtingumas?

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

Ką matuoja amortizuotoji analizė?

1. AVienos brangiausios operacijos bet kurioje sekos vietoje kainą
2. BVidutinę vienos operacijos kainą blogiausio atvejo operacijų sekoje
3. CTikėtiną kainą su atsitiktinėmis įvestimis
4. DAlgoritmo kainą su geriausia įvestimi

Kuris metodas užtikrina tikėtiną O(n log n) greitojo rikiavimo vykdymo laiką bet kokiems įvesties duomenims?

1. ARekursijos taikymas tik kairiajai pusei
2. BVisada pirmojo elemento parinkimas
3. CĮvesties duomenų surikiavimas prieš paleidžiant greitąjį rikiavimą
4. DAtraminio elemento parinkimas atsitiktinai pagal tolygųjį skirstinį

Sustojimo problema parodo, kad:

1. AKai kurios programos greitesniuose kompiuteriuose veikia greičiau, todėl sustojimas priklauso nuo aparatinės įrangos
2. BKiekviena programa anksčiau ar vėliau sustoja
3. CCiklų reikėtų vengti
4. DJoks algoritmas negali kiekvienai programai ir įvesčiai nuspręsti, ar ji sustos