Lembar kerja Algoritma & kompleksitas dengan jawaban

Bagaimana cara kerja selection sort?

1. AMembagi array menjadi dua bagian lalu menggabungkannya
2. BMenyisipkan setiap elemen ke bagian terurut yang terus bertambah dengan menggeser
3. CBerulang kali menukar elemen bersebelahan yang urutannya salah
4. DBerulang kali mencari minimum dari bagian yang belum terurut lalu menukarnya ke depan

Pertumbuhan O(2ⁿ) disebut apa?

1. ALinear
2. BLogaritmik
3. CPolinomial
4. DEksponensial

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Apa artinya suatu masalah memiliki optimal substructure?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Mengapa basis logaritma biasanya tidak dituliskan dalam Big O, seperti pada O(log n)?

1. ASemua logaritma dalam ilmu komputer berbasis 10, sehingga basisnya tersirat
2. BBasis hanya berpengaruh untuk n kecil
3. CLogaritma selalu dibulatkan menjadi bilangan bulat
4. DLogaritma dengan basis berbeda hanya berbeda faktor konstan

Definisi kelas P manakah yang benar?

1. AMasalah keputusan yang dapat diselesaikan algoritma deterministik dalam waktu polinomial
2. BMasalah yang memerlukan waktu eksponensial pada setiap komputer
3. CMasalah yang solusinya dapat diperiksa tetapi tidak pernah dapat ditemukan dalam waktu polinomial
4. DMasalah yang dapat diselesaikan secara paralel

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(2ⁿ) dan ruang O(1)
2. BWaktu O(log n) dan ruang O(n)
3. CWaktu O(n) dan ruang O(n)
4. DWaktu O(n) dan ruang O(1)