Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BHanya dapat diselesaikan dengan mencoba setiap kemungkinan
3. CDapat diselesaikan dalam waktu polinomial
4. DTidak memiliki solusi

Pertumbuhan O(2ⁿ) disebut apa?

1. APolinomial
2. BEksponensial
3. CLinear
4. DLogaritmik

Apa yang dimaksud dengan rekursi?

1. AFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil
2. BSebuah metode pengurutan
3. CSejenis struktur data
4. DLoop yang tidak pernah berakhir

Berapa kompleksitas waktu dari: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Pernyataan mana tentang notasi little-o yang benar?

1. An = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri
2. B2n = o(n), karena 2n tumbuh lambat
3. Cn² = o(n)
4. Dn = o(n²), tetapi n bukan o(n)

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ATermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
2. BDapat diselesaikan dalam waktu polinomial
3. CTidak mungkin diselesaikan
4. DBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem