Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Apa arti f(n) = Θ(g(n))?

1. Af selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah
2. Bf tumbuh benar-benar lebih lambat daripada g
3. Cf tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g
4. Df tumbuh benar-benar lebih cepat daripada g

Pertumbuhan O(2ⁿ) disebut apa?

1. ALogaritmik
2. BPolinomial
3. CLinear
4. DEksponensial

Apa yang diukur oleh analisis amortisasi?

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

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

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

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. AYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
2. BTidak, karena n³ lebih kecil daripada n² untuk n besar
3. CYa, tetapi hanya jika n lebih kecil dari 100
4. DTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu

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

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

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ASetiap perbandingan memerlukan waktu logaritmik
2. BPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
3. CSetiap elemen harus dibandingkan setidaknya sekali
4. DBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan