Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

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

Bagaimana cara kerja selection sort?

1. ABerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan
2. BMembagi array menjadi dua bagian lalu menggabungkannya
3. CMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
4. DBerulang kali menukar elemen bersebelahan yang urutannya salah

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

1. A9 detik
2. B6 detik
3. C3 detik
4. D12 detik

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

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

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

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

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

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

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

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

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AAlgoritma Prim yang dimulai dari satu simpul
2. BAlgoritma Kruskal
3. CFloyd–Warshall
4. DAlgoritma Dijkstra