Lembar kerja Algoritma & kompleksitas dengan jawaban

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

1. ABubble sort
2. BQuicksort
3. CInsertion sort
4. DMerge sort

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

1. A3 detik
2. B9 detik
3. C6 detik
4. D12 detik

Apa syarat binary search terhadap inputnya?

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

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

Pernyataan mana tentang fungsi rekursif tanpa base case yang dapat dicapai yang benar?

1. AFungsi itu terus memanggil dirinya sendiri sampai call stack meluap (overflow)
2. BFungsi itu berjalan dalam waktu O(1)
3. CFungsi itu otomatis mengembalikan 0
4. DKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. ALinear
2. BEksponensial
3. CLogaritmik
4. DKonstan

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. AQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
2. BSeleksi hanya mungkin dilakukan dalam O(n²)
3. CQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk
4. DSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan

Berapa biaya amortisasi menaikkan (increment) penghitung biner, mengingat satu increment dapat membalik banyak bit?

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