Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. A4 detik
2. B2 detik
3. C1 detik
4. D8 detik

Berapa Big O dari 3n² + 5n + 2?

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

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

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

Algoritma greedy:

1. ASelalu memberikan solusi optimal
2. BHanya menggunakan rekursi
3. CMencoba setiap solusi yang mungkin
4. DMengambil pilihan terbaik secara lokal pada setiap langkah

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

1. AO(2ⁿ)
2. BO(n)
3. CO(n²)
4. DO(log 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. CTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
4. DYa, tetapi hanya jika n lebih kecil dari 100

Definisi kelas P manakah yang benar?

1. AMasalah yang dapat diselesaikan secara paralel
2. BMasalah yang solusinya dapat diperiksa tetapi tidak pernah dapat ditemukan dalam waktu polinomial
3. CMasalah yang memerlukan waktu eksponensial pada setiap komputer
4. DMasalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial

Definisi kelas NP manakah yang benar?

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