Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah yang diperlukan oleh carian binari daripada inputnya?

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

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²)

Apakah maksud f(n) = Θ(g(n))?

1. Af tumbuh lebih perlahan daripada g secara ketat
2. Bf tumbuh pada kadar yang sama dengan g, dibatasi atas dan bawah oleh gandaan malar g
3. Cf tumbuh lebih pantas daripada g secara ketat
4. Df sentiasa lebih kecil daripada g bagi setiap n, jadi g membatasinya dari atas tetapi tidak pernah dari bawah

Algoritma tamak (greedy):

1. AHanya menggunakan rekursi
2. BMencuba setiap penyelesaian yang mungkin
3. CSentiasa memberikan penyelesaian optimum
4. DMembuat pilihan terbaik setempat pada setiap langkah

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

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

Apakah masa larian isihan radiks LSD pada n integer dengan d digit dalam asas k?

1. AO(n²)
2. BO(dn log k)
3. CO(d(n + k))
4. DO(n log n)

Bagaimanakah n! dan 2ⁿ dibandingkan untuk n yang besar?

1. An! tumbuh lebih pantas daripada 2ⁿ
2. Bn! ialah O(n²)
3. C2ⁿ tumbuh lebih pantas daripada n!
4. DKeduanya tumbuh pada kadar yang sama

Masalah penghentian (halting problem) menunjukkan bahawa:

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