Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. AAlgoritma Kruskal
2. BAlgoritma Dijkstra
3. CBellman–Ford diperlukan dalam semua kasus
4. DDepth-first search (DFS)

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

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

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

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

Definisi kelas P manakah yang benar?

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

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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