Lembar kerja Algoritma & kompleksitas dengan jawaban

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Manakah dari waktu eksekusi berikut yang polinomial?

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

Bagaimana cara kerja selection sort?

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

1. AΩ(log n)
2. BΩ(n²)
3. CΩ(n log n)
4. DΩ(n)

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

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

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. AAlgoritma Kruskal
2. BDepth-first search (DFS)
3. CAlgoritma Dijkstra
4. DBellman–Ford diperlukan dalam semua kasus

Apakah 2²ⁿ termasuk O(2ⁿ)?

1. ATidak, karena 2²ⁿ = 4ⁿ dan 4ⁿ / 2ⁿ = 2ⁿ tumbuh tanpa batas
2. BTidak, karena 2²ⁿ tumbuh lebih lambat daripada 2ⁿ
3. CYa, karena faktor konstan pada pangkat selalu diabaikan dalam Big O
4. DYa, karena keduanya eksponensial

Definisi kelas NP manakah yang benar?

1. AMasalah yang tidak dapat diselesaikan dalam waktu polinomial
2. BMasalah yang tidak polinomial
3. CMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat
4. DMasalah yang tidak dapat diselesaikan algoritma apa pun