Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah pertumbuhan O(2ⁿ) dipanggil?

1. ALogaritma
2. BLinear
3. CEksponen
4. DPolinomial

Algoritma O(n) mengambil 3 saat untuk n = 1 juta. Kira-kira berapa lamakah ia mengambil masa untuk n = 2 juta?

1. A12 saat
2. B3 saat
3. C9 saat
4. D6 saat

Apakah yang diperlukan oleh carian binari daripada inputnya?

1. APanjang tatasusunan mestilah kuasa dua
2. BTatasusunan mestilah tersusun
3. CTatasusunan mesti mengandungi nombor positif sahaja
4. DTatasusunan tidak boleh mempunyai lebih daripada 1000 elemen

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

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

Isihan pantas sentiasa menggunakan elemen pertama sebagai pangsi. Pada input manakah ia menunjukkan tingkah laku kes terburuk?

1. ATatasusunan dalam susunan rawak
2. BTatasusunan yang sudah tersusun
3. CTatasusunan yang semua elemennya berbeza
4. DTatasusunan sepanjang 2

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

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

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

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

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