Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan memoisasi?

1. AMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
2. BMembebaskan memori setelah fungsi selesai
3. CMenulis komentar di samping setiap baris kode
4. DMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

1. A2 detik
2. B8 detik
3. C1 detik
4. D4 detik

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

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

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. AEksponensial
2. BLogaritmik
3. CKonstan
4. DLinear

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu otomatis mengembalikan 0
2. BFungsi itu berjalan dalam waktu O(1)
3. CFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
4. DKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman

Pengurutan topologis hanya mungkin dilakukan untuk:

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

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. AMasalah itu undecidable
2. BSelalu dapat diselesaikan dalam O(V + E)
3. CMasalah itu NP-hard
4. DDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan