Lembaran kerja Algoritma & kerumitan dengan jawapan

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

Apakah kerumitan masa carian pertama dalam pada graf yang disimpan sebagai senarai bersebelahan?

1. AO(E log V)
2. BO(V²)
3. CO(V × E)
4. DO(V + E)

Notasi manakah yang menerangkan batas atas pertumbuhan?

1. ABig Omega
2. BBig Theta
3. COmega kecil
4. DBig O

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(m + n)
4. DO(mn log n)

Apakah kerumitan masa mendarab dua matriks n × n dengan tiga gelung piawai?

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

Pengaturcaraan dinamik berguna apabila sesuatu masalah mempunyai:

1. ASatu gelung
2. BTiada submasalah langsung, jadi ia boleh diselesaikan dalam satu langkah
3. CSubmasalah bertindih dan substruktur optimum
4. DHanya input rawak

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

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

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. BPokok keputusan dengan n kemungkinan hasil mesti mempunyai kedalaman sekurang-kurangnya log₂ n
3. CSetiap elemen mesti dibandingkan sekurang-kurangnya sekali
4. DPerbandingan mengambil masa logaritma setiap satu