Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah algoritma?

1. AStruktur data yang menyimpan nombor
2. BJujukan langkah yang terhingga dan jelas ditakrifkan yang menyelesaikan masalah
3. CBahasa pengaturcaraan yang direka untuk menulis formula matematik
4. DMana-mana program komputer yang mempunyai antara muka grafik

Masa larian sesuatu algoritma ialah O(n). Apakah pertumbuhan ini dipanggil?

1. AMalar
2. BLogaritma
3. CKuadratik
4. DLinear

Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?

1. AIa sentiasa mengambil tepat satu saat
2. BIa memproses tepat satu elemen bagi setiap saat masa larian
3. CIa hanya boleh dijalankan sekali
4. DMasa larinya tidak bertambah dengan saiz input

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

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

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

1. ALogaritma
2. BEksponen
3. CMalar
4. DLinear

Berapa banyak peringkat yang ada pada rekursi isihan cantum bagi tatasusunan n elemen?

1. AKira-kira n
2. BKira-kira √n
3. CKira-kira log₂ n
4. DKira-kira n / 2

Pernyataan manakah tentang P dan NP yang betul?

1. AMasalah NP tidak boleh disahkan dengan pantas
2. BNP bermaksud "bukan polinomial"
3. CSetiap masalah dalam P juga dalam NP
4. DTelah dibuktikan bahawa P ≠ NP

Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?

1. AW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
2. BKerana n sentiasa kecil
3. CKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
4. DKerana ia hanya berfungsi untuk W = 0