Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

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

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

1. AO(V × E)
2. BO(V + E)
3. CO(V²)
4. DO(E log V)

Algoritma O(n²) memerlukan 1 detik untuk n = 1000. Kira-kira berapa lama untuk n = 2000?

1. A2 detik
2. B1 detik
3. C8 detik
4. D4 detik

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

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

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

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)

Apa akibatnya jika seseorang menemukan algoritma waktu polinomial untuk satu masalah NP-complete?

1. AHanya masalah itu yang pindah ke P
2. BSetiap masalah di NP dapat diselesaikan dalam waktu polinomial, sehingga P = NP
3. CSemua algoritma berwaktu eksponensial seketika berjalan dalam waktu linear
4. DHalting problem menjadi decidable

Untuk varian knapsack mana aturan greedy "ambil item berdasarkan urutan nilai per berat" selalu memberikan jawaban optimal?

1. AKedua varian
2. B0/1 knapsack, ketika item harus selalu diambil utuh
3. CFractional knapsack, ketika item boleh dipecah
4. DTidak ada varian