Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Manakah dari waktu eksekusi berikut yang polinomial?

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

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

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
2. BPilih aktivitas yang dimulai paling awal
3. CPilih aktivitas terpendek terlebih dahulu
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. ATidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input
2. BYa, sehingga batas bawah itu salah
3. CYa, tetapi hanya untuk array yang lebih pendek dari 100
4. DTidak, karena insertion sort bukan pengurutan berbasis perbandingan

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

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