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. BMerge sort
3. CQuicksort
4. DInsertion sort

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

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

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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. ATidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
2. BHanya input acak
3. CSatu loop saja
4. DSubmasalah yang tumpang tindih dan substruktur optimal

Apa artinya suatu masalah memiliki optimal substructure?

1. AMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
2. BSetiap submasalah memiliki ukuran yang sama
3. CSolusi optimal dapat dibangun dari solusi optimal submasalahnya
4. DMasalah itu dapat diselesaikan dalam waktu konstan

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. AMerge sort tidak memiliki struktur rekursif
2. BSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
3. CMerge sort sudah O(n)
4. DDynamic programming hanya bekerja pada masalah graf, bukan pada array

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

1. AHanya masalah itu yang pindah ke P
2. BSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
3. CHalting problem menjadi decidable
4. DSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear

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

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