Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

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

Apa syarat binary search terhadap inputnya?

1. APanjang array harus pangkat dua
2. BArray harus terurut
3. CArray tidak boleh berisi lebih dari 1000 elemen
4. DArray hanya boleh berisi bilangan positif

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig O
2. BBig Omega
3. CLittle omega
4. DBig Theta

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

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

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

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

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

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

Bagaimana travelling salesman problem diklasifikasikan?

1. AVersi keputusannya NP-complete dan versi optimasinya NP-hard
2. BMasalah ini undecidable
3. CMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali
4. DVersi keputusannya di P tetapi versi optimasinya NP-complete

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

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