Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

1. AIa boleh diselesaikan dalam masa malar
2. BIa hanya boleh diselesaikan dengan mencuba setiap kemungkinan
3. CIa tidak mempunyai penyelesaian
4. DIa boleh diselesaikan dalam masa polinomial

Apakah algoritma kekerasan (brute force)?

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

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)

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

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

Carian pertama lebar pada graf tidak berpemberat mencari:

1. ALaluan terpendek dari segi bilangan sisi dari nod permulaan
2. BLaluan terpendek dalam graf yang mengandungi pemberat sisi negatif
3. CSusunan topologi dalam semua graf
4. DPokok rentang minimum

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. BMenunjukkan bahawa X boleh disahkan dalam masa polinomial
3. CMenunjukkan bahawa X tidak mempunyai algoritma polinomial untuk input kecil
4. DMenurunkan masalah NP-sukar yang diketahui kepada X dalam masa polinomial

Mengapakah carian binari tidak memberikan masa O(log n) pada senarai berpaut tunggal?

1. ASampai ke elemen tengah mengambil O(n) langkah, kerana tiada akses indeks langsung
2. BSenarai berpaut tidak boleh disusun
3. CPerbandingan pada nod senarai berpaut lebih perlahan
4. DCarian binari memerlukan memori dua kali ganda