Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah memoisasi?

1. AMenulis komen di sebelah setiap baris kod
2. BMenyimpan hasil panggilan fungsi supaya panggilan berulang dijawab daripada memori
3. CMembebaskan memori selepas fungsi kembali
4. DMenukar rekursi menjadi gelung setara secara automatik supaya tiada tindanan panggilan diperlukan

Apakah yang diperlukan oleh carian binari daripada inputnya?

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

Apakah tiga langkah algoritma bahagi dan takluk?

1. ABahagi, takluk, gabung
2. BBaca, kira, tulis
3. CTeka, semak, ulang
4. DIsih, cari, kembali

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

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

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

1. ASemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
2. BAsas hanya penting untuk n yang kecil
3. CLogaritma sentiasa dibundarkan kepada integer
4. DLogaritma dengan asas berbeza hanya berbeza oleh faktor malar

Sesuatu fungsi menjalankan satu gelung n lelaran dan kemudian, secara berasingan, satu lagi gelung n lelaran. Apakah kerumitan masanya?

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

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

1. AO(n² 2ⁿ)
2. BO(2^n²)
3. CO(n!)
4. DO(n³)

Pernyataan manakah tentang memilih elemen terkecil ke-k dalam tatasusunan tidak tersusun yang betul?

1. AQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
2. BPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan
3. CQuickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
4. DPemilihan hanya mungkin dalam O(n²)