1.Mudah
Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?
- AWaktu untuk input dengan panjang rata-rata
- BWaktu yang diharapkan atas distribusi input berukuran n tertentu
- CWaktu pada komputer yang paling umum
- DNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
2.Mudah
Manakah yang tumbuh paling lambat ketika n menjadi besar?
- AO(n)
- BO(log n)
- CO(n²)
- DO(n log n)
3.Mudah
Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?
- AO(2n)
- BO(n²)
- CO(log n)
- DO(n)
4.Sedang
Berapa kompleksitas waktu kasus terburuk quicksort?
- AO(n)
- BO(log n)
- CO(n²)
- DO(n log n)
5.Sedang
Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?
- AO(1)
- BO(log n)
- CO(n)
- DO(n²)
6.Sedang
Rekurens T(n) = T(n − 1) + O(1) menghasilkan apa?
- AO(log n)
- BO(n²)
- CO(2ⁿ)
- DO(n)
7.Sulit
Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:
- AΘ(n log n)
- BΘ(n²)
- CΘ(n² log n)
- DΘ(n³)
8.Sulit
Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?
- AMemilih pivot secara acak seragam
- BMenggunakan rekursi hanya pada sisi kiri
- CMengurutkan input sebelum menjalankan quicksort
- DSelalu memilih elemen pertama
Kunci jawaban
- 1. B · Waktu yang diharapkan atas distribusi input berukuran n tertentu
- 2. B · O(log n)
- 3. B · O(n²)
- 4. C · O(n²)
- 5. C · O(n)
- 6. D · O(n)
- 7. D · Θ(n³)
- 8. A · Memilih pivot secara acak seragam
Penyelesaian lengkap langkah demi langkah: latih topik ini di examproblems.com.