Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

1. Ao (little o)
2. BO (Big O)
3. CΘ (Big Theta)
4. DΩ (Big Omega)

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Apa yang dimaksud dengan memoisasi?

1. AMenulis komentar di samping setiap baris kode
2. BMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
3. CMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
4. DMembebaskan memori setelah fungsi selesai

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

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

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

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

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

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

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(n) dan ruang O(1)
2. BWaktu O(log n) dan ruang O(n)
3. CWaktu O(2ⁿ) dan ruang O(1)
4. DWaktu O(n) dan ruang O(n)

Bagaimana travelling salesman problem diklasifikasikan?

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