Lembaran kerja Algoritma & kerumitan dengan jawapan

Masa larian manakah yang polinomial?

1. AO(n³)
2. BO(2ⁿ)
3. CO(n!)
4. DO(nⁿ)

Apakah kerumitan masa carian binari pada tatasusunan yang telah disusun?

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

Apakah masa larian isihan kiraan bagi n integer dalam julat 0 hingga k?

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

Mengapakah pengaturcaraan dinamik tidak memberikan pecutan sebenar untuk isihan cantum?

1. ASubmasalahnya tidak bertindih, jadi tiada apa-apa untuk digunakan semula
2. BIsihan cantum tidak mempunyai struktur rekursif
3. CPengaturcaraan dinamik hanya berfungsi pada masalah graf, bukan pada tatasusunan
4. DIsihan cantum sudah O(n)

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

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

1. AMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah
2. BSetiap submasalah mempunyai saiz yang sama
3. CMasalah itu boleh diselesaikan dalam masa malar
4. DPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya

Bagaimanakah masalah jurujual kembara dikelaskan?

1. AVersi keputusan dalam P tetapi versi pengoptimuman NP-lengkap
2. BIa dalam P kerana algoritma Dijkstra menyelesaikannya dengan melawat setiap bandar sekali
3. CIa tidak boleh diputuskan
4. DVersi keputusan ialah NP-lengkap dan versi pengoptimuman ialah NP-sukar

Sesuatu masalah ialah NP-lengkap jika ia:

1. ADalam NP dan setiap masalah NP boleh diturunkan kepadanya dalam masa polinomial
2. BBoleh diselesaikan dalam masa polinomial
3. CDi luar NP tetapi lebih sukar daripada semua masalah NP, seperti masalah penghentian
4. DMustahil diselesaikan