Lembaran kerja Algoritma & kerumitan dengan jawapan

Algoritma dengan dua gelung bersarang, masing-masing berjalan n kali, biasanya mempunyai kerumitan yang mana?

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

Apakah masa larian isihan kiraan bagi n integer dalam julat 0 hingga k?

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

Bagaimanakah isihan pemilihan berfungsi?

1. AIa menyisipkan setiap elemen ke dalam bahagian tersusun yang berkembang dengan menganjak
2. BIa membahagikan tatasusunan kepada dua dan mencantumkannya
3. CIa berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
4. DIa berulang kali menukar elemen jiran yang berada dalam susunan salah

Pernyataan manakah tentang fungsi rekursif tanpa kes asas yang boleh dicapai yang betul?

1. APengkompil sentiasa menukarnya menjadi gelung yang berakhir dengan selamat
2. BIa kembali 0 secara automatik
3. CIa berjalan dalam masa O(1)
4. DIa terus memanggil dirinya sehingga tindanan panggilan melimpah

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

1. ALogaritma sentiasa dibundarkan kepada integer
2. BSemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
3. CLogaritma dengan asas berbeza hanya berbeza oleh faktor malar
4. DAsas hanya penting untuk n yang kecil

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

Apakah perbezaan antara masalah yang tidak boleh diputuskan dengan masalah yang tidak boleh dikendalikan (intractable)?

1. AMasalah tak boleh diputuskan berada dalam NP, manakala masalah tak boleh dikendalikan berada dalam P
2. BMasalah tak boleh dikendalikan tidak dapat diselesaikan oleh sebarang algoritma, manakala yang tak boleh diputuskan hanya memerlukan masa eksponen
3. CMasalah tak boleh diputuskan tiada algoritma untuk semua input; masalah tak boleh dikendalikan ada algoritma, tetapi terlalu perlahan
4. DKedua-duanya bermaksud masalah itu tidak mempunyai algoritma sama sekali

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

1. APaling banyak dua kali ganda saiz litupan bucu minimum
2. BMutunya tidak diketahui berbanding optimum
3. CSentiasa litupan bucu minimum
4. DPaling banyak log n kali minimum