Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa Big O dari 3n² + 5n + 2?

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

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

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

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A12 detik
2. B3 detik
3. C9 detik
4. D6 detik

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. ASubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
2. BDynamic programming hanya bekerja pada masalah graf, bukan pada array
3. CMerge sort tidak memiliki struktur rekursif
4. DMerge sort sudah O(n)

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

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

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

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ATermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
2. BDapat diselesaikan dalam waktu polinomial
3. CTidak mungkin diselesaikan
4. DBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem

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

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