Lembar kerja Algoritma & kompleksitas dengan jawaban

Manakah dari waktu eksekusi berikut yang polinomial?

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

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

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 3
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 4 koin; optimalnya 3
4. DGreedy memakai 3 koin; optimalnya 2

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

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

Apa yang diukur oleh analisis amortisasi?

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

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
2. BKarena n selalu kecil
3. CW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W
4. DKarena algoritma ini hanya berlaku untuk W = 0

Perkalian Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apa hasilnya?

1. AΘ(n^{log₂ 3}), sekitar n^1,585
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n³)