Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. AWaktu untuk input dengan panjang rata-rata
2. BWaktu pada komputer yang paling umum
3. CNilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
4. DWaktu yang diharapkan atas distribusi input berukuran n tertentu

Berapa kompleksitas waktu kasus terburuk merge sort?

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

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

1. AFungsi itu otomatis mengembalikan 0
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 berjalan dalam waktu O(1)

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

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

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

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

Bagaimana travelling salesman problem diklasifikasikan?

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

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. ASeleksi hanya mungkin dilakukan dalam O(n²)
2. BQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
3. CSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
4. DQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk