Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Berapa nilai log₂ 1024?

1. A12
2. B10
3. C512
4. D32

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

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

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

1. AKonstan
2. BEksponensial
3. CLinear
4. DLogaritmik

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

1. AΩ(n)
2. BΩ(log n)
3. CΩ(n log n)
4. DΩ(n²)

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. AQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
2. BSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
3. CSeleksi hanya mungkin dilakukan dalam O(n²)
4. DQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. AMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
2. BTidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat
3. CMasalah undecidable berada di NP, sedangkan masalah intractable di P
4. DKeduanya berarti masalah itu sama sekali tidak memiliki algoritma