Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah maksud f(n) = Θ(g(n))?

1. Af sentiasa lebih kecil daripada g bagi setiap n, jadi g membatasinya dari atas tetapi tidak pernah dari bawah
2. Bf tumbuh pada kadar yang sama dengan g, dibatasi atas dan bawah oleh gandaan malar g
3. Cf tumbuh lebih pantas daripada g secara ketat
4. Df tumbuh lebih perlahan daripada g secara ketat

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

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

Bagaimanakah isihan pemilihan berfungsi?

1. AIa membahagikan tatasusunan kepada dua dan mencantumkannya
2. BIa berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
3. CIa menyisipkan setiap elemen ke dalam bahagian tersusun yang berkembang dengan menganjak
4. DIa berulang kali menukar elemen jiran yang berada dalam susunan salah

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

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

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

1. AO(n² log n)
2. BO(n³)
3. CO(n)
4. DO(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 semua elemennya berbeza
3. CTatasusunan sepanjang 2
4. DTatasusunan yang sudah tersusun

Apakah yang akan menyusul jika seseorang menemui algoritma masa polinomial untuk satu masalah NP-lengkap?

1. ASemua algoritma masa eksponen serta-merta berjalan dalam masa linear
2. BSetiap masalah dalam NP boleh diselesaikan dalam masa polinomial, jadi P = NP
3. CHanya satu masalah itu berpindah ke dalam P
4. DMasalah penghentian menjadi boleh diputuskan

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

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