Lembar kerja Algoritma & kompleksitas dengan jawaban

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar n²
2. BSekitar n / 2
3. CSekitar n
4. DSekitar log₂ n

Berapa nilai log₂ 1024?

1. A512
2. B12
3. C32
4. D10

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

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

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

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

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. AUrutan topologis pada semua graf
2. BLintasan terpendek berdasarkan jumlah sisi dari simpul awal
3. CPohon rentang minimum
4. DLintasan terpendek pada graf yang memiliki bobot sisi negatif

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. AMinimum spanning tree dalam O(E log V)
2. BLintasan terpendek antara semua pasangan simpul dalam O(V³)
3. CUrutan topologis dalam O(V²)
4. DLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, sehingga batas bawah itu salah
3. CYa, tetapi hanya untuk array yang lebih pendek dari 100
4. DTidak, karena insertion sort bukan pengurutan berbasis perbandingan

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. APohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
2. BSetiap perbandingan memerlukan waktu logaritmik
3. CBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
4. DSetiap elemen harus dibandingkan setidaknya sekali