Lembar kerja Algoritma & kompleksitas dengan jawaban

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Manakah dari waktu eksekusi berikut yang polinomial?

1. AO(2ⁿ)
2. BO(nⁿ)
3. CO(n!)
4. DO(n³)

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 100
2. BSekitar 500,000
3. CSekitar 1,000
4. DSekitar 20

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

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

Pengurutan topologis hanya mungkin dilakukan untuk:

1. AGraf berarah asiklik (DAG)
2. BGraf lengkap
3. CGraf dengan bobot negatif
4. DGraf tak berarah

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

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