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)

Berapa banyak memori tambahan yang dipakai merge sort standar berbasis array?

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

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A6 detik
2. B9 detik
3. C3 detik
4. D12 detik

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

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

Algoritma greedy:

1. AHanya menggunakan rekursi
2. BMencoba setiap solusi yang mungkin
3. CMengambil pilihan terbaik secara lokal pada setiap langkah
4. DSelalu memberikan solusi optimal

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

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

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. ABilangan negatif tidak dapat disimpan dalam priority queue
2. BSimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek
3. CAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
4. DAlgoritma itu hanya bekerja pada graf tak berarah

Bagaimana perbandingan n! dan 2ⁿ untuk n besar?

1. AKeduanya tumbuh dengan laju yang sama
2. Bn! tumbuh lebih cepat daripada 2ⁿ
3. C2ⁿ tumbuh lebih cepat daripada n!
4. Dn! adalah O(n²)