Lembaran kerja Algoritma & kerumitan dengan jawapan

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 kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

1. AIa boleh diselesaikan dalam masa malar
2. BIa boleh diselesaikan dalam masa polinomial
3. CIa hanya boleh diselesaikan dengan mencuba setiap kemungkinan
4. DIa tidak mempunyai penyelesaian

Betulkah untuk mengatakan bahawa algoritma O(n²) juga O(n³)?

1. ATidak, kerana n³ lebih kecil daripada n² untuk n yang besar
2. BTidak, kerana Big O mesti sentiasa menyatakan kadar pertumbuhan yang tepat bagi fungsi itu
3. CYa, kerana Big O ialah batas atas dan n² tumbuh tidak lebih pantas daripada n³
4. DYa, tetapi hanya jika n kurang daripada 100

Apakah kerumitan masa mengira nombor Fibonacci ke-n dengan jadual bawah-atas?

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

Algoritma tamak (greedy):

1. AMembuat pilihan terbaik setempat pada setiap langkah
2. BMencuba setiap penyelesaian yang mungkin
3. CSentiasa memberikan penyelesaian optimum
4. DHanya menggunakan rekursi

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

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

Pernyataan manakah tentang P dan NP yang betul?

1. ASetiap masalah dalam P juga dalam NP
2. BTelah dibuktikan bahawa P ≠ NP
3. CMasalah NP tidak boleh disahkan dengan pantas
4. DNP bermaksud "bukan polinomial"