Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud base case pada fungsi rekursif?

1. APemanggilan yang memakai memori paling banyak
2. BKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
3. CBaris pertama fungsi
4. DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Apa yang diukur oleh analisis amortisasi?

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

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
2. BInsertion sort adalah O(n log n) pada kasus terburuk
3. CAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. AHanya input acak
2. BSatu loop saja
3. CSubmasalah yang tumpang tindih dan substruktur optimal
4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah

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

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

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

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