Lembar kerja Algoritma & kompleksitas dengan jawaban

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. AMerge sort
2. BQuicksort
3. CHeap sort
4. DBubble sort

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. ALogaritmik
2. BKonstan
3. CKuadratik
4. DLinear

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

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 500,000
2. BSekitar 100
3. CSekitar 1,000
4. DSekitar 20

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 2 koin; optimalnya 2
2. BGreedy memakai 3 koin; optimalnya 3
3. CGreedy memakai 3 koin; optimalnya 2
4. DGreedy memakai 4 koin; optimalnya 3

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. ASelalu dapat diselesaikan dalam O(V + E)
2. BDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
3. CMasalah itu undecidable
4. DMasalah itu NP-hard

Apa yang ditetapkan oleh teorema Cook–Levin?

1. ABoolean satisfiability problem (SAT) adalah NP-complete
2. BP tidak sama dengan NP
3. CSetiap masalah NP dapat diselesaikan dalam waktu eksponensial
4. DHalting problem tidak dapat diputuskan (undecidable)