Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah algoritma kekerasan (brute force)?

1. AYang sentiasa menggunakan rekursi
2. BYang berjalan pada banyak pemproses
3. CYang mencuba semua calon penyelesaian yang mungkin
4. DYang meneka jawapan secara rawak

Apakah rekursi?

1. AGelung yang tidak pernah berakhir
2. BSejenis struktur data
3. CKaedah isihan
4. DFungsi yang memanggil dirinya sendiri pada input yang lebih kecil

Apakah kerumitan masa carian pertama dalam pada graf yang disimpan sebagai senarai bersebelahan?

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

Dengan syiling 1, 3 dan 4 dan jumlah 6, berapa banyak syiling yang digunakan oleh kaedah tamak "syiling terbesar dahulu", berbanding optimum?

1. ATamak menggunakan 2 syiling; optimum ialah 2
2. BTamak menggunakan 3 syiling; optimum ialah 2
3. CTamak menggunakan 3 syiling; optimum ialah 3
4. DTamak menggunakan 4 syiling; optimum ialah 3

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

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

Dalam tatasusunan tersusun, anda mencari dua elemen yang jumlahnya sama dengan sasaran dengan menggerakkan satu penunjuk dari setiap hujung ke dalam. Apakah kerumitan masanya?

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

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 log n)
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)