Lembar kerja Algoritma & kompleksitas dengan jawaban

Kompleksitas ruang (space complexity) mengukur:

1. AJumlah baris kode
2. BUkuran fisik komputer
3. CJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
4. DRuang disk yang dipakai file program setelah dikompilasi

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

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Berapa banyak ruang stack yang dipakai fungsi faktorial rekursif sederhana fact(n) = n × fact(n − 1)?

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

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray dalam urutan acak
2. BArray yang sudah terurut
3. CArray yang semua elemennya berbeda
4. DArray dengan panjang 2

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Teknik manakah yang memberikan waktu eksekusi harapan (expected) O(n log n) untuk quicksort pada input apa pun?

1. AMengurutkan input sebelum menjalankan quicksort
2. BMemilih pivot secara acak seragam
3. CSelalu memilih elemen pertama
4. DMenggunakan rekursi hanya pada sisi kiri

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. AMasalah itu undecidable
2. BDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan
3. CSelalu dapat diselesaikan dalam O(V + E)
4. DMasalah itu NP-hard