Lembaran kerja Algoritma & kerumitan dengan jawapan

Kerumitan ruang mengukur:

1. ASaiz fizikal komputer
2. BBilangan baris kod
3. CJumlah memori yang diperlukan algoritma apabila input bertambah
4. DRuang cakera fail program setelah ia dikompil

Apakah kerumitan masa carian binari pada tatasusunan yang telah disusun?

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

Apakah kerumitan masa mencari nilai terbesar dalam tatasusunan tidak tersusun yang mengandungi n nombor?

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

Algoritma isihan manakah yang stabil?

1. AIsihan cantum
2. BIsihan pantas (versi dalam-tempat biasa)
3. CIsihan timbunan
4. DIsihan pemilihan (versi biasa)

Apakah yang diukur oleh analisis teramortisasi?

1. AKos algoritma pada input terbaik
2. BKos dijangka merentasi input rawak
3. CKos satu operasi yang paling mahal di mana-mana dalam jujukan itu
4. DKos purata bagi setiap operasi merentasi jujukan operasi kes terburuk

Kira-kira berapa banyak perbandingan yang diperlukan oleh carian binari dalam kes terburuk pada tatasusunan tersusun 1,000,000 elemen?

1. AKira-kira 500,000
2. BKira-kira 100
3. CKira-kira 1,000
4. DKira-kira 20

Dua perkara manakah yang mesti ditunjukkan untuk membuktikan bahawa masalah keputusan X ialah NP-lengkap?

1. AX dalam NP, dan masalah NP-lengkap yang diketahui boleh diturunkan kepada X dalam masa polinomial
2. BX boleh diturunkan kepada masalah dalam P, dan X dalam NP
3. CX dalam P, dan X boleh diturunkan kepada SAT
4. DX tiada algoritma polinomial, dan X boleh diputuskan

Algoritma Strassen mendarab matriks menggunakan 7 dan bukannya 8 pendaraban rekursif blok separuh saiz. Apakah masa larinya?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), kira-kira n^2.81
4. DΘ(n³)