Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. ASelalu memerlukan tepat satu detik
2. BHanya dapat dijalankan sekali
3. CWaktu eksekusinya tidak bertambah seiring ukuran input
4. DMemproses tepat satu elemen per detik waktu eksekusi

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada input terkecil
2. BWaktu yang diperlukan pada komputer yang lambat
3. CWaktu yang diharapkan pada input acak berukuran n
4. DWaktu maksimum yang diperlukan atas semua input berukuran n

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. ABubble sort
2. BQuicksort
3. CMerge sort
4. DHeap sort

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 3
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 4 koin; optimalnya 3
4. DGreedy memakai 3 koin; optimalnya 2

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

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

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

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