Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa arti f(n) = Θ(g(n))?

1. Af tumbuh benar-benar lebih lambat daripada g
2. Bf selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah
3. Cf tumbuh benar-benar lebih cepat daripada g
4. Df tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g

Apa yang dimaksud base case pada fungsi rekursif?

1. APemanggilan yang memakai memori paling banyak
2. BKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi
3. CBaris pertama fungsi
4. DKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun

Algoritma pengurutan mana yang memilih pivot dan mempartisi array menjadi elemen yang lebih kecil dan lebih besar?

1. ABubble sort
2. BMerge sort
3. CInsertion sort
4. DQuicksort

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 3 koin; optimalnya 3
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 4 koin; optimalnya 3
4. DGreedy memakai 3 koin; optimalnya 2

Rekurens T(n) = T(n − 1) + O(1) menghasilkan apa?

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

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. AUrutan topologis pada semua graf
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CLintasan terpendek berdasarkan jumlah sisi dari simpul awal
4. DPohon rentang minimum

Berapa kompleksitas waktu dari: for i = 1 to n: for (j = i; j ≤ n; j = j + i) lakukan kerja O(1)?

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

Algoritma Strassen mengalikan matriks memakai 7, bukan 8, perkalian rekursif blok berukuran setengah. Berapa waktu eksekusinya?

1. AΘ(n² log n)
2. BΘ(n^{log₂ 7}), sekitar n^2,81
3. CΘ(n²)
4. DΘ(n³)