Lembaran kerja Algoritma & kerumitan dengan jawapan

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

Apakah maksudnya jika sesuatu operasi berjalan dalam masa O(1)?

1. AMasa larinya tidak bertambah dengan saiz input
2. BIa memproses tepat satu elemen bagi setiap saat masa larian
3. CIa sentiasa mengambil tepat satu saat
4. DIa hanya boleh dijalankan sekali

Apakah kes asas bagi fungsi rekursif?

1. APanggilan yang menggunakan paling banyak memori
2. BKes dengan input terbesar, yang dikendalikan sebelum sebarang panggilan rekursif
3. CBaris pertama fungsi
4. DKes yang dijawab terus tanpa membuat panggilan rekursif lain

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

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

1. ASetiap submasalah mempunyai saiz yang sama
2. BMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah
3. CPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya
4. DMasalah itu boleh diselesaikan dalam masa malar

Bagaimanakah algoritma Prim membina pokok rentang minimum?

1. AIa mengisih semua sisi mengikut pemberat dan menambah setiap satu kecuali jika ia membentuk kitaran dalam hutan
2. BIa membuang sisi paling mahal sehingga tiada kitaran tinggal
3. CIa menjalankan carian pertama lebar dan mengekalkan pokok BFS
4. DIa menumbuhkan satu pokok dari bucu permulaan, dengan menambah sisi termurah yang meninggalkan pokok

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

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

Menggunakan teorem induk, T(n) = 8T(n/2) + O(n²) mempunyai penyelesaian:

1. AΘ(n²)
2. BΘ(n² log n)
3. CΘ(n log n)
4. DΘ(n³)