Lembaran kerja Algoritma & kerumitan dengan jawapan

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

1. AIa boleh diselesaikan dalam masa malar
2. BIa tidak mempunyai penyelesaian
3. CIa hanya boleh diselesaikan dengan mencuba setiap kemungkinan
4. DIa boleh diselesaikan dalam masa polinomial

Berapa banyak memori tambahan yang digunakan oleh isihan cantum berasaskan tatasusunan piawai?

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

Apakah algoritma kekerasan (brute force)?

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

Apakah kerumitan masa bagi: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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(log n)
2. BO(n)
3. CO(n log n)
4. DO(n²)

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

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

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

1. APaling banyak dua kali ganda saiz litupan bucu minimum
2. BSentiasa litupan bucu minimum
3. CPaling banyak log n kali minimum
4. DMutunya tidak diketahui berbanding optimum

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

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