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)

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

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

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(mn log n)
2. BO(mn)
3. CO(2^m+n)
4. DO(m + n)

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

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

Breadth-first search (BFS) pada graf tak berbobot menemukan:

1. ALintasan terpendek berdasarkan jumlah sisi dari simpul awal
2. BLintasan terpendek pada graf yang memiliki bobot sisi negatif
3. CPohon rentang minimum
4. DUrutan topologis pada semua graf

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

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

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