Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

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. CKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
4. DBaris pertama fungsi

Apa yang dimaksud dengan algoritma?

1. AUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
2. BBahasa pemrograman yang dirancang untuk menulis rumus matematika
3. CSetiap program komputer yang memiliki antarmuka grafis
4. DStruktur data yang menyimpan bilangan

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

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

1. AUrutan topologis pada semua graf
2. BPohon rentang minimum
3. CLintasan terpendek pada graf yang memiliki bobot sisi negatif
4. DLintasan terpendek berdasarkan jumlah sisi dari simpul awal

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Definisi kelas NP manakah yang benar?

1. AMasalah yang tidak polinomial
2. BMasalah yang tidak dapat diselesaikan algoritma apa pun
3. CMasalah yang tidak dapat diselesaikan dalam waktu polinomial
4. DMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat