Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah algoritma kekerasan (brute force)?

1. AYang meneka jawapan secara rawak
2. BYang mencuba semua calon penyelesaian yang mungkin
3. CYang berjalan pada banyak pemproses
4. DYang sentiasa menggunakan rekursi

Notasi manakah yang menerangkan batas bawah pertumbuhan?

1. AΘ (Big Theta)
2. BO (Big O)
3. Co (o kecil)
4. DΩ (Big Omega)

Apakah kerumitan masa kes terburuk isihan cantum?

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

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

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

Sesuatu fungsi menjalankan satu gelung n lelaran dan kemudian, secara berasingan, satu lagi gelung n lelaran. Apakah kerumitan masanya?

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

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

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

Apakah yang akan menyusul jika seseorang menemui algoritma masa polinomial untuk satu masalah NP-lengkap?

1. ASemua algoritma masa eksponen serta-merta berjalan dalam masa linear
2. BSetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
3. CHanya satu masalah itu berpindah ke dalam P
4. DMasalah penghentian menjadi boleh diputuskan

Mengapakah sebarang carian berasaskan perbandingan dalam tatasusunan tersusun memerlukan Ω(log n) perbandingan dalam kes terburuk?

1. APerbandingan mengambil masa logaritma setiap satu
2. BPokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
3. CSetiap elemen mesti dibandingkan sekurang-kurangnya sekali
4. DCarian binari ialah satu-satunya algoritma yang mungkin, dan ia memerlukan log₂ n perbandingan