Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

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

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

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

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

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

1. AEksponensial
2. BKonstan
3. CLinear
4. DLogaritmik

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 log n)
2. BO(n²)
3. CO(n √n)
4. DO(n)

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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