Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Apa tiga langkah algoritma divide and conquer?

1. ADivide, conquer, combine (bagi, taklukkan, gabungkan)
2. BBaca, hitung, tulis
3. CUrutkan, cari, kembalikan
4. DTebak, periksa, ulangi

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

1. AKonstan
2. BLogaritmik
3. CKuadratik
4. DLinear

Apa artinya suatu masalah memiliki optimal substructure?

1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
2. BSetiap submasalah memiliki ukuran yang sama
3. CMasalah itu dapat diselesaikan dalam waktu konstan
4. DSolusi optimal dapat dibangun dari solusi optimal submasalahnya

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. ALintasan terpendek pada graf yang memiliki bobot sisi negatif
2. BLintasan terpendek berdasarkan jumlah sisi dari simpul awal
3. CUrutan topologis pada semua graf
4. DPohon rentang minimum

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar n
2. BSekitar n / 2
3. CSekitar √n
4. DSekitar log₂ n

Apa yang ditetapkan oleh teorema Cook–Levin?

1. ASetiap masalah NP dapat diselesaikan dalam waktu eksponensial
2. BHalting problem tidak dapat diputuskan (undecidable)
3. CBoolean satisfiability problem (SAT) adalah NP-complete
4. DP tidak sama dengan NP

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²), tetapi n bukan o(n)
4. Dn² = o(n)