Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa kes terburuk isihan cantum?

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

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

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

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)

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

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

Hubungan jadi semula T(n) = 2T(n/2) + O(n) mempunyai penyelesaian:

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

Apakah kerumitan masa kes terburuk isihan pantas?

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

Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?

1. AKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
2. BW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
3. CKerana ia hanya berfungsi untuk W = 0
4. DKerana n sentiasa kecil

Mengapakah algoritma Dijkstra boleh memberikan keputusan yang salah apabila sesetengah pemberat sisi negatif?

1. ASesuatu bucu dimuktamadkan apabila dikeluarkan, tetapi sisi negatif kemudian masih boleh memberinya laluan yang lebih pendek
2. BNombor negatif tidak boleh disimpan dalam baris gilir keutamaan
3. CIa masuk ke dalam gelung tak terhingga pada setiap sisi negatif
4. DIa hanya berfungsi pada graf tidak berarah