Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

1. AO(V × E)
2. BO(V + E)
3. CO(V²)
4. DO(E log V)

Kompleksitas ruang (space complexity) mengukur:

1. ARuang disk yang dipakai file program setelah dikompilasi
2. BJumlah memori yang dibutuhkan algoritma seiring bertambahnya input
3. CUkuran fisik komputer
4. DJumlah baris kode

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. AEksponensial
2. BLogaritmik
3. CKonstan
4. DLinear

Suatu masalah disebut NP-complete jika masalah tersebut:

1. ADapat diselesaikan dalam waktu polinomial
2. BTermasuk dalam NP dan setiap masalah NP dapat direduksi ke masalah tersebut dalam waktu polinomial
3. CTidak mungkin diselesaikan
4. DBerada di luar NP tetapi lebih sulit daripada semua masalah NP, seperti halting problem

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

1. AO(V³)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V × E)