Lembar kerja Algoritma & kompleksitas dengan jawaban

Kompleksitas ruang (space complexity) mengukur:

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

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Apa yang dimaksud dengan algoritma?

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

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

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. ALogaritmik
2. BLinear
3. CEksponensial
4. DKonstan

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

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

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

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

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AFloyd–Warshall
2. BAlgoritma Kruskal
3. CAlgoritma Dijkstra
4. DAlgoritma Prim yang dimulai dari satu simpul