Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. APanjang array harus pangkat dua
2. BArray tidak boleh berisi lebih dari 1000 elemen
3. CArray harus terurut
4. DArray hanya boleh berisi bilangan positif

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AHanya dapat dijalankan sekali
2. BWaktu eksekusinya tidak bertambah seiring ukuran input
3. CMemproses tepat satu elemen per detik waktu eksekusi
4. DSelalu memerlukan tepat satu detik

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

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

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

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

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

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

1. AO(1)
2. BO(n)
3. CO(n²)
4. DO(log 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. 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. DSeleksi hanya mungkin dilakukan dalam O(n²)

Pernyataan manakah tentang P dan NP yang benar?

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