Lembaran kerja Algoritma & kerumitan dengan jawapan

Notasi manakah yang menerangkan batas bawah pertumbuhan?

1. AΩ (Big Omega)
2. BO (Big O)
3. Co (o kecil)
4. DΘ (Big Theta)

Apakah algoritma?

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

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

1. AO(n²)
2. BO(1)
3. CO(log n)
4. DO(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. BLogaritma dengan asas berbeza hanya berbeza oleh faktor malar
3. CLogaritma sentiasa dibundarkan kepada integer
4. DAsas hanya penting untuk n yang kecil

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

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

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

Mengapakah sebarang carian berasaskan perbandingan dalam tatasusunan tersusun memerlukan Ω(log n) perbandingan dalam kes terburuk?

1. ASetiap elemen mesti dibandingkan sekurang-kurangnya sekali
2. BPerbandingan mengambil masa logaritma setiap satu
3. CPokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
4. DCarian binari ialah satu-satunya algoritma yang mungkin, dan ia memerlukan log₂ n perbandingan

Teknik manakah yang memberikan masa larian dijangka O(n log n) bagi isihan pantas pada sebarang input?

1. AMengisih input sebelum menjalankan isihan pantas
2. BMenggunakan rekursi pada sebelah kiri sahaja
3. CSentiasa memilih elemen pertama
4. DMemilih pangsi secara seragam rawak