Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

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

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A6 detik
2. B12 detik
3. C3 detik
4. D9 detik

Manakah dari waktu eksekusi berikut yang polinomial?

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

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. AUrutan topologis dalam O(V²)
2. BMinimum spanning tree dalam O(E log V)
3. CLintasan terpendek antara semua pasangan simpul dalam O(V³)
4. DLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu berjalan dalam waktu O(1)
2. BFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
3. CKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
4. DFungsi itu otomatis mengembalikan 0

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

Bagaimana travelling salesman problem diklasifikasikan?

1. AMasalah ini undecidable
2. BVersi keputusannya di P tetapi versi optimasinya NP-complete
3. CMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali
4. DVersi keputusannya NP-complete dan versi optimasinya NP-hard

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

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