Lembaran kerja Algoritma & kerumitan dengan jawapan

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 algoritma?

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

Apakah kerumitan masa kes terbaik isihan sisipan, pada tatasusunan yang sudah tersusun?

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

Algoritma tamak (greedy):

1. AHanya menggunakan rekursi
2. BMembuat pilihan terbaik setempat pada setiap langkah
3. CMencuba setiap penyelesaian yang mungkin
4. DSentiasa memberikan penyelesaian optimum

Apakah kerumitan masa teramortisasi bagi menambah pada tatasusunan dinamik yang menggandakan kapasitinya apabila penuh?

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

Dengan syiling 1, 3 dan 4 dan jumlah 6, berapa banyak syiling yang digunakan oleh kaedah tamak "syiling terbesar dahulu", berbanding optimum?

1. ATamak menggunakan 4 syiling; optimum ialah 3
2. BTamak menggunakan 2 syiling; optimum ialah 2
3. CTamak menggunakan 3 syiling; optimum ialah 3
4. DTamak menggunakan 3 syiling; optimum ialah 2

Apakah perbezaan antara masalah yang tidak boleh diputuskan dengan masalah yang tidak boleh dikendalikan (intractable)?

1. AMasalah tak boleh diputuskan tiada algoritma untuk semua input; masalah tak boleh dikendalikan ada algoritma, tetapi terlalu perlahan
2. BMasalah tak boleh diputuskan berada dalam NP, manakala masalah tak boleh dikendalikan berada dalam P
3. CKedua-duanya bermaksud masalah itu tidak mempunyai algoritma sama sekali
4. DMasalah tak boleh dikendalikan tidak dapat diselesaikan oleh sebarang algoritma, manakala yang tak boleh diputuskan hanya memerlukan masa eksponen

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

1. AMasalah penghentian menjadi boleh diputuskan
2. BSetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
3. CSemua algoritma masa eksponen serta-merta berjalan dalam masa linear
4. DHanya satu masalah itu berpindah ke dalam P