Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

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

1. AQuicksort
2. BMerge sort
3. CInsertion sort
4. DBubble sort

Bagaimana algoritma Prim membangun minimum spanning tree?

1. AMengurutkan semua sisi berdasarkan bobot dan menambahkan masing-masing kecuali jika membentuk siklus dalam hutan
2. BMenghapus sisi termahal sampai tidak ada siklus tersisa
3. CMenjalankan breadth-first search dan menyimpan pohon BFS
4. DMenumbuhkan satu pohon dari simpul awal, setiap kali menambahkan sisi termurah yang keluar dari pohon

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Algoritma dynamic programming Held–Karp menyelesaikan travelling salesman problem secara eksak. Berapa waktu eksekusinya untuk n kota?

1. AO(2^n²)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(n³)

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

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