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 baris kode
4. DJumlah memori yang dibutuhkan algoritma seiring bertambahnya input

Algoritma dengan dua loop bersarang, yang masing-masing berjalan n kali, biasanya memiliki kompleksitas apa?

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

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ABig Theta
2. BBig O
3. CLittle omega
4. DBig Omega

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon
2. BMenghapus sisi termahal sampai tidak ada siklus tersisa
3. CMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
4. DMenjalankan breadth-first search dan menyimpan pohon BFS

Algoritma greedy:

1. AHanya menggunakan rekursi
2. BSelalu memberikan solusi optimal
3. CMencoba setiap solusi yang mungkin
4. DMengambil pilihan terbaik secara lokal pada setiap langkah

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

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

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

Definisi kelas NP manakah yang benar?

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