Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu pada komputer yang paling umum
2. BNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
3. CWaktu yang diharapkan atas distribusi input berukuran n tertentu
4. DWaktu untuk input dengan panjang rata-rata

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar n
2. BSekitar log₂ n
3. CSekitar n²
4. DSekitar n / 2

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu maksimum yang diperlukan atas semua input berukuran n
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu yang diperlukan pada komputer yang lambat
4. DWaktu yang diperlukan pada input terkecil

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

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

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

Berapa banyak tingkat rekursi merge sort untuk array berisi n elemen?

1. ASekitar log₂ n
2. BSekitar n
3. CSekitar √n
4. DSekitar n / 2

Apa yang ditetapkan oleh teorema Cook–Levin?

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

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. ACircuit satisfiability
2. B2-SAT, dengan setiap klausa berisi paling banyak dua literal
3. CSAT umum pada formula dalam bentuk normal konjungtif
4. D3-SAT, dengan setiap klausa berisi tepat tiga literal