Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah tiga langkah algoritma bahagi dan takluk?

1. ABahagi, takluk, gabung
2. BBaca, kira, tulis
3. CTeka, semak, ulang
4. DIsih, cari, kembali

Yang manakah tumbuh paling perlahan apabila n menjadi besar?

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

Apakah pertumbuhan O(2ⁿ) dipanggil?

1. AEksponen
2. BPolinomial
3. CLogaritma
4. DLinear

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

1. AMasalah itu boleh diselesaikan dalam masa malar
2. BPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya
3. CSetiap submasalah mempunyai saiz yang sama
4. DMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah

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

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

Isihan pantas sentiasa menggunakan elemen pertama sebagai pangsi. Pada input manakah ia menunjukkan tingkah laku kes terburuk?

1. ATatasusunan yang sudah tersusun
2. BTatasusunan yang semua elemennya berbeza
3. CTatasusunan sepanjang 2
4. DTatasusunan dalam susunan rawak

Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?

1. AKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
2. BW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
3. CKerana n sentiasa kecil
4. DKerana ia hanya berfungsi untuk W = 0

Masalah penghentian (halting problem) menunjukkan bahawa:

1. AGelung harus dielakkan
2. BSesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
3. CSetiap program akhirnya berhenti
4. DTiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti