Lembar kerja Algoritma & kompleksitas dengan jawaban

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. ALogaritmik
2. BKuadratik
3. CLinear
4. DKonstan

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

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

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

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

Definisi kelas P manakah yang benar?

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

Mengambil kedua titik ujung dari setiap sisi dalam maximal matching menghasilkan vertex cover. Seberapa baik cover ini?

1. AKualitasnya tidak diketahui dibandingkan optimum
2. BPaling banyak dua kali ukuran minimum vertex cover
3. CSelalu merupakan minimum vertex cover
4. DPaling banyak log n kali minimum