Lembar kerja Algoritma & kompleksitas dengan jawaban

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

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

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

Apa syarat binary search terhadap inputnya?

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

Algoritma greedy:

1. AMencoba setiap solusi yang mungkin
2. BHanya menggunakan rekursi
3. CMengambil pilihan terbaik secara lokal pada setiap langkah
4. DSelalu memberikan solusi optimal

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

1. AΩ(n log n)
2. BΩ(log n)
3. CΩ(n²)
4. DΩ(n)

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

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

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

1. APaling banyak dua kali ukuran minimum vertex cover
2. BKualitasnya tidak diketahui dibandingkan optimum
3. CPaling banyak log n kali minimum
4. DSelalu merupakan minimum vertex cover

Definisi kelas P manakah yang benar?

1. AMasalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial
2. BMasalah yang dapat diselesaikan secara paralel
3. CMasalah yang solusinya dapat diperiksa tetapi tidak pernah dapat ditemukan dalam waktu polinomial
4. DMasalah yang memerlukan waktu eksponensial pada setiap komputer