Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa carian linear dalam tatasusunan tidak tersusun dengan n elemen (kes terburuk)?

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

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

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

Algoritma dengan dua gelung bersarang, masing-masing berjalan n kali, biasanya mempunyai kerumitan yang mana?

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

Dalam tatasusunan tersusun, anda mencari dua elemen yang jumlahnya sama dengan sasaran dengan menggerakkan satu penunjuk dari setiap hujung ke dalam. Apakah kerumitan masanya?

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

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 20
3. CKira-kira 100
4. DKira-kira 1,000

Algoritma isihan manakah yang stabil?

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

Masalah penghentian (halting problem) menunjukkan bahawa:

1. ASesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
2. BSetiap program akhirnya berhenti
3. CGelung harus dielakkan
4. DTiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti

Laluan ringkas terpendek boleh dicari dalam masa polinomial. Apakah yang diketahui tentang mencari laluan ringkas terpanjang antara dua bucu dalam graf am?

1. AIa boleh diselesaikan oleh algoritma Dijkstra dengan pemberat dinegatifkan
2. BIa tidak boleh diputuskan
3. CIa sentiasa boleh diselesaikan dalam O(V + E)
4. DIa NP-sukar