Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

Apa tiga langkah algoritma divide and conquer?

1. AUrutkan, cari, kembalikan
2. BTebak, periksa, ulangi
3. CDivide, conquer, combine (bagi, taklukkan, gabungkan)
4. DBaca, hitung, tulis

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

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

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ALogaritma dengan basis berbeda hanya berbeda faktor konstan
2. BLogaritma selalu dibulatkan menjadi bilangan bulat
3. CSemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
4. DBasis hanya berpengaruh untuk n kecil

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. ADapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
2. BMasalah itu undecidable
3. CSelalu dapat diselesaikan dalam O(V + E)
4. DMasalah itu NP-hard

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

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