Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

Apakah yang diperlukan oleh carian binari daripada inputnya?

1. ATatasusunan mesti mengandungi nombor positif sahaja
2. BPanjang tatasusunan mestilah kuasa dua
3. CTatasusunan tidak boleh mempunyai lebih daripada 1000 elemen
4. DTatasusunan mestilah tersusun

Yang manakah tumbuh paling perlahan apabila n menjadi besar?

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

Apakah penyelesaian hubungan jadi semula T(n) = T(n − 1) + O(n)?

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

Algoritma manakah yang mencari laluan terpendek dari satu sumber dalam graf dengan pemberat sisi tidak negatif?

1. ABellman–Ford diperlukan dalam semua kes
2. BAlgoritma Kruskal
3. CCarian pertama dalam
4. DAlgoritma Dijkstra

Carian pertama lebar pada graf tidak berpemberat mencari:

1. APokok rentang minimum
2. BSusunan topologi dalam semua graf
3. CLaluan terpendek dalam graf yang mengandungi pemberat sisi negatif
4. DLaluan terpendek dari segi bilangan sisi dari nod permulaan

Isihan sisipan berjalan dalam O(n) pada input tersusun. Adakah ini bercanggah dengan batas bawah Ω(n log n) untuk isihan perbandingan?

1. AYa, tetapi hanya untuk tatasusunan lebih pendek daripada 100
2. BTidak, batas bawah terpakai pada kes terburuk merentasi semua input, bukan pada setiap input
3. CYa, oleh itu batas bawah itu salah
4. DTidak, kerana isihan sisipan bukan isihan perbandingan

Menggunakan teorem induk, T(n) = 8T(n/2) + O(n²) mempunyai penyelesaian:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)