Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu untuk input dengan panjang rata-rata
2. BWaktu yang diharapkan atas distribusi input berukuran n tertentu
3. CNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
4. DWaktu pada komputer yang paling umum

Kompleksitas ruang (space complexity) mengukur:

1. AJumlah baris kode
2. BUkuran fisik komputer
3. CJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
4. DRuang disk yang dipakai file program setelah dikompilasi

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diharapkan pada input acak berukuran n
2. BWaktu yang diperlukan pada komputer yang lambat
3. CWaktu yang diperlukan pada input terkecil
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Rekurens T(n) = T(n − 1) + O(1) menghasilkan apa?

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ABerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem
2. BTidak mungkin diselesaikan
3. CDapat diselesaikan dalam waktu polinomial
4. DTermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. ACircuit satisfiability
2. B3-SAT, dengan setiap klausa berisi tepat tiga literal
3. CSAT umum pada formula dalam bentuk normal konjungtif
4. D2-SAT, dengan setiap klausa berisi paling banyak dua literal