Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan rekursi?

1. ASebuah metode pengurutan
2. BLoop yang tidak pernah berakhir
3. CSejenis struktur data
4. DFungsi yang memanggil dirinya sendiri dengan input yang lebih kecil

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

1. AO(n²)
2. BO(n log n)
3. CO(1)
4. DO(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 yang diharapkan atas distribusi input berukuran n tertentu
4. DWaktu pada komputer yang paling umum

Berapa kompleksitas waktu menghitung bilangan Fibonacci ke-n dengan tabel bottom-up?

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

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut
3. CInsertion sort adalah O(n log n) pada kasus terburuk
4. DInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

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

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. ASimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek
2. BAlgoritma itu hanya bekerja pada graf tak berarah
3. CAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
4. DBilangan negatif tidak dapat disimpan dalam priority queue