Lembaran kerja Algoritma & kerumitan dengan jawapan

Apakah kerumitan masa kes terburuk isihan sisipan?

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

Apakah Big O bagi 3n² + 5n + 2?

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

Apakah rekursi?

1. AGelung yang tidak pernah berakhir
2. BKaedah isihan
3. CSejenis struktur data
4. DFungsi yang memanggil dirinya sendiri pada input yang lebih kecil

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

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

Apakah maksudnya sesuatu masalah mempunyai substruktur optimum?

1. AMasalah itu boleh diselesaikan dalam masa malar
2. BMasalah itu mempunyai tepat satu penyelesaian optimum, yang dikongsi oleh setiap submasalah
3. CSetiap submasalah mempunyai saiz yang sama
4. DPenyelesaian optimum boleh dibina daripada penyelesaian optimum submasalahnya

Berapa banyak ruang tindanan yang digunakan oleh fungsi faktorial rekursif mudah fact(n) = n × fact(n − 1)?

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

Pernyataan manakah tentang memilih elemen terkecil ke-k dalam tatasusunan tidak tersusun yang betul?

1. APemilihan sentiasa memerlukan Ω(n log n) kerana ia memerlukan pengisihan
2. BPemilihan hanya mungkin dalam O(n²)
3. CQuickselect berjalan dalam O(log n) kes terburuk, kerana ia berekursi pada satu sebelah pangsi sahaja
4. DQuickselect berjalan dalam O(n) dijangka, dan median-bagi-median menjamin O(n) kes terburuk

Mengambil kedua-dua hujung setiap sisi dalam padanan maksimal memberikan litupan bucu. Sebaik manakah litupan ini?

1. APaling banyak dua kali ganda saiz litupan bucu minimum
2. BPaling banyak log n kali minimum
3. CSentiasa litupan bucu minimum
4. DMutunya tidak diketahui berbanding optimum