Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

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

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

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig Omega
2. BBig Theta
3. CLittle omega
4. DBig O

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

1. ADepth-first search (DFS)
2. BBellman–Ford diperlukan dalam semua kasus
3. CAlgoritma Dijkstra
4. DAlgoritma Kruskal

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. ATidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
2. BTidak, karena n³ lebih kecil daripada n² untuk n besar
3. CYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
4. DYa, tetapi hanya jika n lebih kecil dari 100

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

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

Berapa kompleksitas waktu dari: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Bagaimana algoritma Bellman–Ford mendeteksi siklus berbobot negatif yang dapat dicapai dari sumber?

1. AAlgoritma menjalankan Dijkstra dua kali dan membandingkan kedua hasil jaraknya
2. BAlgoritma menghitung siklus dengan depth-first search
3. CSetelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
4. DAlgoritma memeriksa apakah ada sisi berbobot negatif