Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. AKuadratik
2. BLinear
3. CKonstan
4. DLogaritmik

Apa artinya jika suatu operasi berjalan dalam waktu O(1)?

1. AMemproses tepat satu elemen per detik waktu eksekusi
2. BWaktu eksekusinya tidak bertambah seiring ukuran input
3. CSelalu memerlukan tepat satu detik
4. DHanya dapat dijalankan sekali

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)

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

1. AUrutan topologis pada semua graf
2. BPohon rentang minimum
3. CLintasan terpendek berdasarkan jumlah sisi dari simpul awal
4. DLintasan terpendek pada graf yang memiliki bobot sisi negatif

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Pernyataan mana tentang notasi little-o yang benar?

1. An = o(n), karena setiap fungsi adalah little-o dari dirinya sendiri
2. B2n = o(n), karena 2n tumbuh lambat
3. Cn² = o(n)
4. Dn = o(n²), tetapi n bukan o(n)

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ASetiap elemen harus dibandingkan setidaknya sekali
2. BPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n
3. CBinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
4. DSetiap perbandingan memerlukan waktu logaritmik