Lembaran kerja Algoritma & kerumitan dengan jawapan

Sesuatu masalah biasanya dipanggil boleh dikendalikan (tractable) jika:

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

Apakah kerumitan masa kes terburuk isihan sisipan?

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

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

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

Mengapakah asas logaritma biasanya ditinggalkan dalam Big O, seperti dalam O(log n)?

1. ASemua logaritma dalam sains komputer berasas 10, jadi ia tersirat
2. BLogaritma dengan asas berbeza hanya berbeza oleh faktor malar
3. CAsas hanya penting untuk n yang kecil
4. DLogaritma sentiasa dibundarkan kepada integer

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

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

Algoritma isihan manakah yang stabil?

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

Pernyataan manakah tentang notasi o kecil yang betul?

1. An² = o(n)
2. Bn = o(n), kerana setiap fungsi ialah o kecil bagi dirinya sendiri
3. Cn = o(n²), tetapi n bukan o(n)
4. D2n = o(n), kerana 2n tumbuh perlahan

Bagaimanakah masalah jurujual kembara dikelaskan?

1. AVersi keputusan dalam P tetapi versi pengoptimuman NP-lengkap
2. BVersi keputusan ialah NP-lengkap dan versi pengoptimuman ialah NP-sukar
3. CIa dalam P kerana algoritma Dijkstra menyelesaikannya dengan melawat setiap bandar sekali
4. DIa tidak boleh diputuskan