Lembar kerja Algoritma & kompleksitas dengan jawaban

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. CStruktur data yang menyimpan bilangan
4. DSetiap program komputer yang memiliki antarmuka grafis

Pertumbuhan O(2ⁿ) disebut apa?

1. AEksponensial
2. BLinear
3. CLogaritmik
4. DPolinomial

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang menebak jawaban secara acak
2. BAlgoritma yang berjalan di banyak prosesor
3. CAlgoritma yang mencoba semua kandidat solusi yang mungkin
4. DAlgoritma yang selalu memakai rekursi

Apa yang diukur oleh analisis amortisasi?

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

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

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

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

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

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

1. AO(n² 2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(2^n²)

Definisi kelas NP manakah yang benar?

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