Lembar kerja Algoritma & kompleksitas dengan jawaban

Kompleksitas ruang (space complexity) mengukur:

1. AUkuran fisik komputer
2. BRuang disk yang dipakai file program setelah dikompilasi
3. CJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
4. DJumlah baris kode

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Manakah dari waktu eksekusi berikut yang polinomial?

1. AO(2ⁿ)
2. BO(n³)
3. CO(n!)
4. DO(nⁿ)

Apa artinya suatu masalah memiliki optimal substructure?

1. ASolusi optimal dapat dibangun dari solusi optimal submasalahnya
2. BMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
3. CSetiap submasalah memiliki ukuran yang sama
4. DMasalah itu dapat diselesaikan dalam waktu konstan

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³)
4. DO(n log n)

Berapa kompleksitas waktu kasus terburuk quicksort?

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

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. APerbandingan pada node linked list lebih lambat
2. BMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung
3. CBinary search memerlukan setidaknya dua kali lipat memori
4. DLinked list tidak dapat diurutkan

Untuk varian knapsack mana aturan greedy "ambil item berdasarkan urutan nilai per berat" selalu memberikan jawaban optimal?

1. AFractional knapsack, ketika item boleh dipecah
2. BTidak ada varian
3. CKedua varian
4. D0/1 knapsack, ketika item harus selalu diambil utuh