Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan memoisasi?

1. AMenulis komentar di samping setiap baris kode
2. BMembebaskan memori setelah fungsi selesai
3. CMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
4. DMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori

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

1. A12 detik
2. B6 detik
3. C3 detik
4. D9 detik

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

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

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

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

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

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

Masalah penghentian (halting problem) menunjukkan bahwa:

1. ABeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
2. BLoop sebaiknya dihindari
3. CTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
4. DSetiap program pada akhirnya akan berhenti

Algoritma manakah yang menemukan pohon rentang minimum dengan berulang kali menambahkan sisi termurah yang tidak membentuk siklus?

1. AAlgoritma Kruskal
2. BAlgoritma Prim yang dimulai dari satu simpul
3. CFloyd–Warshall
4. DAlgoritma Dijkstra