Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Apa syarat binary search terhadap inputnya?

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

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

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

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

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

1. ABellman–Ford diperlukan dalam semua kasus
2. BAlgoritma Kruskal
3. CDepth-first search (DFS)
4. DAlgoritma Dijkstra

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. APohon rentang minimum
2. BUrutan topologis pada semua graf
3. CLintasan terpendek pada graf yang memiliki bobot sisi negatif
4. DLintasan terpendek berdasarkan jumlah sisi dari simpul awal

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

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

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

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