Lembar kerja Algoritma & kompleksitas dengan jawaban

Notasi manakah yang menyatakan batas bawah (lower bound) pertumbuhan?

1. AΘ (Big Theta)
2. BO (Big O)
3. Co (little o)
4. DΩ (Big Omega)

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BTidak memiliki solusi
3. CHanya dapat diselesaikan dengan mencoba setiap kemungkinan
4. DDapat diselesaikan dalam waktu polinomial

Berapa Big O dari 3n² + 5n + 2?

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

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

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

Algoritma pengurutan manakah yang stabil (stable)?

1. AQuicksort (versi in-place yang umum)
2. BHeap sort
3. CSelection sort (versi yang umum)
4. DMerge sort

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort adalah O(n log n) pada kasus terburuk
3. CInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut

Definisi kelas P manakah yang benar?

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

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AAlgoritma Prim yang dimulai dari satu simpul
2. BAlgoritma Dijkstra
3. CAlgoritma Kruskal
4. DFloyd–Warshall