Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa carian binari pada tatasusunan yang telah disusun?

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

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

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

Apakah yang diperlukan oleh carian binari daripada inputnya?

1. ATatasusunan mesti mengandungi nombor positif sahaja
2. BPanjang tatasusunan mestilah kuasa dua
3. CTatasusunan mestilah tersusun
4. DTatasusunan tidak boleh mempunyai lebih daripada 1000 elemen

Kira-kira berapa banyak perbandingan yang diperlukan oleh carian binari dalam kes terburuk pada tatasusunan tersusun 1,000,000 elemen?

1. AKira-kira 100
2. BKira-kira 500,000
3. CKira-kira 1,000
4. DKira-kira 20

Algoritma isihan manakah yang stabil?

1. AIsihan timbunan
2. BIsihan cantum
3. CIsihan pemilihan (versi biasa)
4. DIsihan pantas (versi dalam-tempat biasa)

Apakah kerumitan masa mendarab dua matriks n × n dengan tiga gelung piawai?

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

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 boleh disahkan dalam masa polinomial
4. DMenunjukkan bahawa X tidak mempunyai algoritma polinomial untuk input kecil

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

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