Lembaran kerja Algoritma & kerumitan dengan jawapan

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

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

Apakah pertumbuhan O(2ⁿ) dipanggil?

1. ALogaritma
2. BLinear
3. CPolinomial
4. DEksponen

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

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

Berapa banyak ruang tindanan yang digunakan oleh fungsi faktorial rekursif mudah fact(n) = n × fact(n − 1)?

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

Anda mengisih tatasusunan n elemen sekali dan kemudian menjawab k pertanyaan keahlian dengan carian binari. Apakah jumlah kosnya?

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

Apakah kerumitan masa algoritma pengaturcaraan dinamik piawai bagi subjujukan sepunya terpanjang untuk rentetan sepanjang m dan n?

1. AO(mn)
2. BO(2^m+n)
3. CO(mn log n)
4. DO(m + n)

Apakah yang akan menyusul jika seseorang menemui algoritma masa polinomial untuk satu masalah NP-lengkap?

1. ASetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
2. BHanya satu masalah itu berpindah ke dalam P
3. CMasalah penghentian menjadi boleh diputuskan
4. DSemua algoritma masa eksponen serta-merta berjalan dalam masa linear

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

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