Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang selalu memakai rekursi
2. BAlgoritma yang menebak jawaban secara acak
3. CAlgoritma yang mencoba semua kandidat solusi yang mungkin
4. DAlgoritma yang berjalan di banyak prosesor

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Pertumbuhan O(2ⁿ) disebut apa?

1. ALogaritmik
2. BPolinomial
3. CEksponensial
4. DLinear

Algoritma greedy:

1. ASelalu memberikan solusi optimal
2. BHanya menggunakan rekursi
3. CMengambil pilihan terbaik secara lokal pada setiap langkah
4. DMencoba setiap solusi yang mungkin

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

1. ABellman–Ford diperlukan dalam semua kasus
2. BAlgoritma Dijkstra
3. CDepth-first search (DFS)
4. DAlgoritma Kruskal

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. ATidak, karena n³ lebih kecil daripada n² untuk n besar
2. BYa, tetapi hanya jika n lebih kecil dari 100
3. CYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³
4. DTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu

Batas mana yang benar untuk log(n!)?

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

Definisi kelas P manakah yang benar?

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