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. BStruktur data yang menyimpan bilangan
3. CSetiap program komputer yang memiliki antarmuka grafis
4. DBahasa pemrograman yang dirancang untuk menulis rumus matematika

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ALittle omega
2. BBig Omega
3. CBig O
4. DBig Theta

Bagaimana cara kerja selection sort?

1. ABerulang kali menukar elemen bersebelahan yang urutannya salah
2. BBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
3. CMembagi array menjadi dua bagian lalu menggabungkannya
4. DMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 500,000
2. BSekitar 20
3. CSekitar 100
4. DSekitar 1,000

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

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

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

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

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. ASeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
2. BSeleksi hanya mungkin dilakukan dalam O(n²)
3. CQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk
4. DQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot

Untuk varian knapsack mana aturan greedy "ambil item berdasarkan urutan nilai per berat" selalu memberikan jawaban optimal?

1. AKedua varian
2. BFractional knapsack, ketika item boleh dipecah
3. CTidak ada varian
4. D0/1 knapsack, ketika item harus selalu diambil utuh