Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu pada komputer yang paling umum
2. BWaktu yang diharapkan atas distribusi input berukuran n tertentu
3. CWaktu untuk input dengan panjang rata-rata
4. DNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk

Apa yang dimaksud dengan algoritma?

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

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

Algoritma pengurutan manakah yang stabil (stable)?

1. AHeap sort
2. BQuicksort (versi in-place yang umum)
3. CSelection sort (versi yang umum)
4. DMerge sort

Apa artinya suatu masalah memiliki optimal substructure?

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

Berapa kompleksitas waktu membangun binary heap dari n elemen tidak terurut dengan metode bottom-up?

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

Definisi kelas P manakah yang benar?

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