Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. AKonstan
2. BLogaritmik
3. CLinear
4. DKuadratik

Suatu masalah biasanya disebut tractable jika:

1. ATidak memiliki solusi
2. BDapat diselesaikan dalam waktu polinomial
3. CDapat diselesaikan dalam waktu konstan
4. DHanya dapat diselesaikan dengan mencoba setiap kemungkinan

Apa yang diukur oleh analisis amortisasi?

1. ABiaya yang diharapkan atas input acak
2. BBiaya rata-rata per operasi atas urutan operasi kasus terburuk
3. CBiaya satu operasi yang paling mahal di mana pun dalam urutan itu
4. DBiaya algoritma pada input terbaik

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) = T(n − 1) + O(1) menghasilkan apa?

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

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

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

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf dengan bobot negatif
2. BGraf tak berarah
3. CGraf berarah asiklik (DAG)
4. DGraf lengkap