Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. ANilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
2. BWaktu untuk input dengan panjang rata-rata
3. CWaktu pada komputer yang paling umum
4. DWaktu yang diharapkan atas distribusi input berukuran n tertentu

Bagaimana algoritma Prim membangun minimum spanning tree?

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

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

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

Berapa kompleksitas waktu algoritma Bellman–Ford pada graf dengan V simpul dan E sisi?

1. AO(V + E)
2. BO(E log V)
3. CO(V × E)
4. DO(V³ × E)

Masalah knapsack 0/1 yang diselesaikan dengan pemrograman dinamis memerlukan waktu O(nW). Mengapa ini disebut pseudo-polinomial?

1. AKarena n selalu kecil
2. BKarena algoritma ini hanya berlaku untuk W = 0
3. CKarena algoritmanya bersifat acak (randomised) dan waktu eksekusinya berbeda untuk setiap input
4. DW adalah nilai numerik, sehingga waktunya eksponensial terhadap jumlah bit yang diperlukan untuk menuliskan W

Berapa kompleksitas waktu membangun binary heap dari n elemen tidak terurut dengan metode bottom-up?

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