Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. AMerge sort
2. BHeap sort
3. CQuicksort
4. DBubble sort

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

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

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

1. AO(log n)
2. BO(1)
3. CO(n log 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 20
3. CSekitar 500,000
4. DSekitar 100

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. ABellman–Ford diperlukan dalam semua kasus
2. BAlgoritma Kruskal
3. CAlgoritma Dijkstra
4. DDepth-first search (DFS)

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ASetiap perbandingan memerlukan waktu logaritmik
2. BPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
3. CBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
4. DSetiap elemen harus dibandingkan setidaknya sekali

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
2. BMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
3. CMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
4. DMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial