Lembaran kerja Algoritma & kerumitan dengan jawapan

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

Apakah tiga langkah algoritma bahagi dan takluk?

1. ABaca, kira, tulis
2. BTeka, semak, ulang
3. CBahagi, takluk, gabung
4. DIsih, cari, kembali

Kerumitan ruang mengukur:

1. ABilangan baris kod
2. BJumlah memori yang diperlukan algoritma apabila input bertambah
3. CSaiz fizikal komputer
4. DRuang cakera fail program setelah ia dikompil

Algoritma tamak (greedy):

1. AMembuat pilihan terbaik setempat pada setiap langkah
2. BSentiasa memberikan penyelesaian optimum
3. CHanya menggunakan rekursi
4. DMencuba setiap penyelesaian yang mungkin

Isihan pantas sentiasa menggunakan elemen pertama sebagai pangsi. Pada input manakah ia menunjukkan tingkah laku kes terburuk?

1. ATatasusunan yang semua elemennya berbeza
2. BTatasusunan sepanjang 2
3. CTatasusunan yang sudah tersusun
4. DTatasusunan dalam susunan rawak

Apakah masa larian isihan radiks LSD pada n integer dengan d digit dalam asas k?

1. AO(n log n)
2. BO(n²)
3. CO(dn log k)
4. DO(d(n + k))

Apakah kos masa dan ruang mengira nombor Fibonacci ke-n dengan gelung yang hanya menyimpan dua nilai terakhir?

1. AMasa O(log n) dan ruang O(n)
2. BMasa O(2ⁿ) dan ruang O(1)
3. CMasa O(n) dan ruang O(1)
4. DMasa O(n) dan ruang O(n)

Isihan sisipan berjalan dalam O(n) pada input tersusun. Adakah ini bercanggah dengan batas bawah Ω(n log n) untuk isihan perbandingan?

1. ATidak, batas bawah terpakai pada kes terburuk merentasi semua input, bukan pada setiap input
2. BTidak, kerana isihan sisipan bukan isihan perbandingan
3. CYa, oleh itu batas bawah itu salah
4. DYa, tetapi hanya untuk tatasusunan lebih pendek daripada 100