Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

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²)

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BDapat diselesaikan dalam waktu polinomial
3. CHanya dapat diselesaikan dengan mencoba setiap kemungkinan
4. DTidak memiliki solusi

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. ATidak, karena n³ lebih kecil daripada n² untuk n besar
2. BTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
3. CYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
4. DYa, tetapi hanya jika n lebih kecil dari 100

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

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

Algoritma greedy:

1. AMengambil pilihan terbaik secara lokal pada setiap langkah
2. BMencoba setiap solusi yang mungkin
3. CSelalu memberikan solusi optimal
4. DHanya menggunakan rekursi

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. CSetiap elemen harus dibandingkan setidaknya sekali
4. DBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan

Pernyataan manakah tentang P dan NP yang benar?

1. ASetiap masalah di P juga termasuk dalam NP
2. BTelah dibuktikan bahwa P ≠ NP
3. CMasalah NP tidak dapat diverifikasi dengan cepat
4. DNP berarti "not polynomial"