Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa kes terburuk isihan cantum?

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

Apakah kerumitan masa mencari nilai terbesar dalam tatasusunan tidak tersusun yang mengandungi n nombor?

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

Algoritma O(n²) mengambil 1 saat untuk n = 1000. Kira-kira berapa lamakah ia mengambil masa untuk n = 2000?

1. A8 saat
2. B2 saat
3. C1 saat
4. D4 saat

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

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

Apakah penyelesaian hubungan jadi semula T(n) = T(n/2) + O(1)?

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

Betulkah untuk mengatakan bahawa algoritma O(n²) juga O(n³)?

1. ATidak, kerana Big O mesti sentiasa menyatakan kadar pertumbuhan yang tepat bagi fungsi itu
2. BTidak, kerana n³ lebih kecil daripada n² untuk n yang besar
3. CYa, tetapi hanya jika n kurang daripada 100
4. DYa, kerana Big O ialah batas atas dan n² tumbuh tidak lebih pantas daripada n³

Masalah kebolehpuasan manakah yang diketahui boleh diselesaikan dalam masa polinomial?

1. A3-SAT, yang setiap klausanya mempunyai tepat tiga literal
2. B2-SAT, yang setiap klausanya mempunyai paling banyak dua literal
3. CSAT am pada formula dalam bentuk normal konjungtif
4. DKebolehpuasan litar

Untuk menunjukkan bahawa masalah baharu X ialah NP-sukar, apakah yang mesti anda lakukan?

1. AMenurunkan X kepada masalah NP-sukar yang diketahui dalam masa polinomial
2. BMenurunkan masalah NP-sukar yang diketahui kepada X dalam masa polinomial
3. CMenunjukkan bahawa X tidak mempunyai algoritma polinomial untuk input kecil
4. DMenunjukkan bahawa X boleh disahkan dalam masa polinomial