Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Algoritma pengurutan manakah yang berulang kali menukar elemen bersebelahan yang urutannya salah?

1. AMerge sort
2. BBubble sort
3. CQuicksort
4. DHeap sort

Apa syarat binary search terhadap inputnya?

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

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

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

1. ALintasan terpendek berdasarkan jumlah sisi dari simpul awal
2. BUrutan topologis pada semua graf
3. CPohon rentang minimum
4. DLintasan terpendek pada graf yang memiliki bobot sisi negatif

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. AMerge sort sudah O(n)
2. BSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
3. CDynamic programming hanya bekerja pada masalah graf, bukan pada array
4. DMerge sort tidak memiliki struktur rekursif

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. A2-SAT, dengan setiap klausa berisi paling banyak dua literal
2. B3-SAT, dengan setiap klausa berisi tepat tiga literal
3. CSAT umum pada formula dalam bentuk normal konjungtif
4. DCircuit satisfiability

Bagaimana algoritma Bellman–Ford mendeteksi siklus berbobot negatif yang dapat dicapai dari sumber?

1. ASetelah V − 1 putaran, algoritma memeriksa apakah masih ada sisi yang dapat direlaksasi
2. BAlgoritma memeriksa apakah ada sisi berbobot negatif
3. CAlgoritma menjalankan Dijkstra dua kali dan membandingkan kedua hasil jaraknya
4. DAlgoritma menghitung siklus dengan depth-first search