Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah yang diperlukan oleh carian binari daripada inputnya?

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

Apakah kes asas bagi fungsi rekursif?

1. AKes yang dijawab terus tanpa membuat panggilan rekursif lain
2. BKes dengan input terbesar, yang dikendalikan sebelum sebarang panggilan rekursif
3. CPanggilan yang menggunakan paling banyak memori
4. DBaris pertama fungsi

Apakah kerumitan masa mencari nilai terbesar dalam tatasusunan tidak tersusun yang mengandungi n nombor?

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

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

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

Dalam masalah pemilihan aktiviti, peraturan tamak manakah yang sentiasa memberikan bilangan maksimum aktiviti yang tidak bertindih?

1. APilih aktiviti terpendek dahulu
2. BPilih aktiviti yang tamat paling awal, kemudian ulang dengan yang serasi
3. CPilih aktiviti yang bermula paling awal
4. DPilih aktiviti dengan pertindihan paling sedikit dahulu, kemudian ulang dengan yang serasi

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 4 syiling; optimum ialah 3
2. BTamak menggunakan 2 syiling; optimum ialah 2
3. CTamak menggunakan 3 syiling; optimum ialah 3
4. DTamak menggunakan 3 syiling; optimum ialah 2

Masalah kebolehpuasan manakah yang diketahui boleh diselesaikan dalam masa polinomial?

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

Pendaraban Karatsuba memenuhi T(n) = 3T(n/2) + O(n). Apakah penyelesaiannya?

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n^{log₂ 3}), kira-kira n^1.585
4. DΘ(n log n)