Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah masa larian isihan kiraan bagi n integer dalam julat 0 hingga k?

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

Apakah log₂ 1024?

1. A10
2. B32
3. C512
4. D12

Apakah Big O bagi 3n² + 5n + 2?

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

Kerumitan masa Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) ialah:

1. ALinear
2. BLogaritma
3. CMalar
4. DEksponen

Apakah kerumitan masa algoritma pengaturcaraan dinamik piawai bagi subjujukan sepunya terpanjang untuk rentetan sepanjang m dan n?

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

Kira-kira berapa banyak perbandingan yang diperlukan oleh carian binari dalam kes terburuk pada tatasusunan tersusun 1,000,000 elemen?

1. AKira-kira 1,000
2. BKira-kira 100
3. CKira-kira 20
4. DKira-kira 500,000

Laluan ringkas terpendek boleh dicari dalam masa polinomial. Apakah yang diketahui tentang mencari laluan ringkas terpanjang antara dua bucu dalam graf am?

1. AIa tidak boleh diputuskan
2. BIa NP-sukar
3. CIa boleh diselesaikan oleh algoritma Dijkstra dengan pemberat dinegatifkan
4. DIa sentiasa boleh diselesaikan dalam O(V + E)

Masalah kebolehpuasan manakah yang diketahui boleh diselesaikan dalam masa polinomial?

1. ASAT am pada formula dalam bentuk normal konjungtif
2. B3-SAT, yang setiap klausanya mempunyai tepat tiga literal
3. C2-SAT, yang setiap klausanya mempunyai paling banyak dua literal
4. DKebolehpuasan litar