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²)
3. CO(E log V)
4. DO(V × E)

Apa syarat binary search terhadap inputnya?

1. APanjang array harus pangkat dua
2. BArray harus terurut
3. CArray tidak boleh berisi lebih dari 1000 elemen
4. DArray hanya boleh berisi bilangan positif

Berapa kompleksitas waktu linear search pada array tidak terurut berisi n elemen (kasus terburuk)?

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

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AInsertion sort adalah O(n log n) pada kasus terburuk
2. BInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
3. CInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
4. DAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen

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

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

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

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

Batas mana yang benar untuk log(n!)?

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

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

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