Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. ABubble sort
2. BInsertion sort
3. CMerge sort
4. DQuicksort

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang selalu memakai rekursi
2. BAlgoritma yang berjalan di banyak prosesor
3. CAlgoritma yang mencoba semua kandidat solusi yang mungkin
4. DAlgoritma yang menebak jawaban secara acak

Berapa Big O dari 3n² + 5n + 2?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

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

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

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

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

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