Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah algoritma?

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

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

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

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

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

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

Apakah kerumitan masa mendarab dua matriks n × n dengan tiga gelung piawai?

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

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

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

Masalah kebolehpuasan manakah yang diketahui boleh diselesaikan dalam masa polinomial?

1. A3-SAT, yang setiap klausanya mempunyai tepat tiga literal
2. B2-SAT, yang setiap klausanya mempunyai paling banyak dua literal
3. CSAT am pada formula dalam bentuk normal konjungtif
4. DKebolehpuasan litar

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. BQuickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk
3. CPemilihan hanya mungkin dalam O(n²)
4. DPemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan