Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu polinomial
2. BHanya dapat diselesaikan dengan mencoba setiap kemungkinan
3. CDapat diselesaikan dalam waktu konstan
4. DTidak memiliki solusi

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

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

1. AInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
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. DAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Apa yang ditetapkan oleh teorema Cook–Levin?

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

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. BPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
3. CSetiap perbandingan memerlukan waktu logaritmik
4. DSetiap elemen harus dibandingkan setidaknya sekali