Lembar kerja Algoritma & kompleksitas dengan jawaban

Kompleksitas ruang (space complexity) mengukur:

1. AUkuran fisik komputer
2. BJumlah baris kode
3. CRuang disk yang dipakai file program setelah dikompilasi
4. DJumlah memori yang dibutuhkan algoritma seiring bertambahnya input

Apa syarat binary search terhadap inputnya?

1. AArray harus terurut
2. BArray hanya boleh berisi bilangan positif
3. CPanjang array harus pangkat dua
4. DArray tidak boleh berisi lebih dari 1000 elemen

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

1. A1 detik
2. B4 detik
3. C2 detik
4. D8 detik

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

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

1. AO(k n log n)
2. BO(nk)
3. CO(n log n + k log n)
4. DO(n + k)

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
2. BMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
3. CMenghapus sisi termahal sampai tidak ada siklus tersisa
4. DMenjalankan breadth-first search dan menyimpan pohon BFS

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
2. BMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
3. CMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
4. DMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil

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²)
4. DΘ(n log n)