Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

1. AStruktur data yang menyimpan bilangan
2. BSetiap program komputer yang memiliki antarmuka grafis
3. CBahasa pemrograman yang dirancang untuk menulis rumus matematika
4. DUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang selalu memakai rekursi
2. BAlgoritma yang mencoba semua kandidat solusi yang mungkin
3. CAlgoritma yang menebak jawaban secara acak
4. DAlgoritma yang berjalan di banyak prosesor

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. ASatu loop saja
2. BHanya input acak
3. CSubmasalah yang tumpang tindih dan substruktur optimal
4. DTidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah

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

1. ALintasan terpendek berdasarkan jumlah sisi dari simpul awal
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CPohon rentang minimum
4. DUrutan topologis pada semua graf

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

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

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. ATidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas
2. BTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
3. CYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
4. DYa, karena keduanya eksponensial