Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah tiga langkah algoritma bahagi dan takluk?

1. ATeka, semak, ulang
2. BBaca, kira, tulis
3. CIsih, cari, kembali
4. DBahagi, takluk, gabung

Strategi reka bentuk manakah yang digunakan oleh isihan cantum?

1. ABahagi dan takluk
2. BPilihan tamak
3. CKekerasan (brute force)
4. DPengaturcaraan dinamik

Apakah kerumitan masa kes terburuk isihan sisipan?

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

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

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

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

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

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

1. AO(V³ × E)
2. BO(V × E)
3. CO(V + E)
4. DO(E log V)

Pernyataan manakah tentang notasi o kecil yang betul?

1. An = o(n), kerana setiap fungsi ialah o kecil bagi dirinya sendiri
2. Bn = o(n²), tetapi n bukan o(n)
3. Cn² = o(n)
4. D2n = o(n), kerana 2n tumbuh perlahan

Masalah penghentian (halting problem) menunjukkan bahawa:

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