Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Strategi desain apa yang digunakan merge sort?

1. APilihan greedy
2. BDivide and conquer (bagi dan taklukkan)
3. CBrute force
4. DDynamic programming

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada input terkecil
2. BWaktu maksimum yang diperlukan atas semua input berukuran n
3. CWaktu yang diharapkan pada input acak berukuran n
4. DWaktu yang diperlukan pada komputer yang lambat

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 500,000
2. BSekitar 1,000
3. CSekitar 20
4. DSekitar 100

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

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

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

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

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf lengkap
2. BGraf tak berarah
3. CGraf dengan bobot negatif
4. DGraf berarah asiklik (DAG)

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

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