Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa yang dimaksud dengan algoritma?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas terpendek terlebih dahulu
2. BPilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
3. CPilih aktivitas yang dimulai paling awal
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
2. BAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
3. CInsertion sort adalah O(n log n) pada kasus terburuk
4. DInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

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

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. AKeduanya berarti masalah itu sama sekali tidak memiliki algoritma
2. BMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
3. CMasalah undecidable berada di NP, sedangkan masalah intractable di P
4. DTidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat