Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

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

1. AMerge sort
2. BInsertion sort
3. CBubble sort
4. DQuicksort

Apa yang dimaksud dengan rekursi?

1. ASejenis struktur data
2. BLoop yang tidak pernah berakhir
3. CSebuah metode pengurutan
4. DFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. AUrutan topologis pada semua graf
2. BPohon rentang minimum
3. CLintasan terpendek berdasarkan jumlah sisi dari simpul awal
4. DLintasan terpendek pada graf yang memiliki bobot sisi negatif

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
3. CInsertion sort adalah O(n log n) pada kasus terburuk
4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut

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

1. ATidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
2. BTidak, karena n³ lebih kecil daripada n² untuk n besar
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

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. AHalting problem menjadi decidable
2. BHanya masalah itu yang pindah ke P
3. CSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear
4. DSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, karena insertion sort bukan pengurutan berbasis perbandingan
2. BYa, sehingga batas bawah itu salah
3. CYa, tetapi hanya untuk array yang lebih pendek dari 100
4. DTidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input