Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

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

Apa arti f(n) = Θ(g(n))?

1. Af tumbuh benar-benar lebih lambat daripada g
2. Bf tumbuh benar-benar lebih cepat daripada g
3. Cf selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah
4. Df tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

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

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. BKompiler selalu mengubahnya menjadi loop yang berakhir dengan aman
3. CFungsi itu berjalan dalam waktu O(1)
4. DFungsi itu otomatis mengembalikan 0

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. ALintasan terpendek antara semua pasangan simpul dalam O(V³)
2. BMinimum spanning tree dalam O(E log V)
3. CUrutan topologis dalam O(V²)
4. DLintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)

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

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

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
2. BMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
3. CMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil
4. DMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial