Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma?

1. ASetiap program komputer yang memiliki antarmuka grafis
2. BStruktur data yang menyimpan bilangan
3. CUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah
4. DBahasa pemrograman yang dirancang untuk menulis rumus matematika

Apa yang dimaksud dengan memoisasi?

1. AMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
2. BMembebaskan memori setelah fungsi selesai
3. CMenulis komentar di samping setiap baris kode
4. DMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

1. AO(dn log k)
2. BO(d(n + k))
3. CO(n²)
4. DO(n log n)

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

1. AO(n)
2. BO(1)
3. CO(n log n)
4. DO(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 2 koin; optimalnya 2
2. BGreedy memakai 4 koin; optimalnya 3
3. CGreedy memakai 3 koin; optimalnya 2
4. DGreedy memakai 3 koin; optimalnya 3

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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

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

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