Lembaran kerja Algoritma & kerumitan dengan jawapan

Mengakses elemen mengikut indeks dalam tatasusunan mengambil masa:

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

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

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

Satu gelung bermula dengan i = 1 dan menggandakan i pada setiap lelaran sehingga i > n. Berapa banyak lelaran yang dijalankannya?

1. AKira-kira n²
2. BKira-kira n / 2
3. CKira-kira log₂ n
4. DKira-kira n

Algoritma isihan manakah yang stabil?

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

Apakah kerumitan masa algoritma Bellman–Ford pada graf dengan V bucu dan E sisi?

1. AO(V³ × E)
2. BO(V + E)
3. CO(E log V)
4. DO(V × E)

Apakah kerumitan masa algoritma pengaturcaraan dinamik piawai bagi subjujukan sepunya terpanjang untuk rentetan sepanjang m dan n?

1. AO(m + n)
2. BO(mn log n)
3. CO(mn)
4. DO(2^m+n)

Masalah penghentian (halting problem) menunjukkan bahawa:

1. ATiada algoritma yang dapat memutuskan bagi setiap program dan input sama ada ia berhenti
2. BGelung harus dielakkan
3. CSesetengah program berjalan lebih pantas pada komputer yang lebih pantas, jadi penghentian bergantung pada perkakasan
4. DSetiap program akhirnya berhenti

Apakah perbezaan antara masalah yang tidak boleh diputuskan dengan masalah yang tidak boleh dikendalikan (intractable)?

1. AKedua-duanya bermaksud masalah itu tidak mempunyai algoritma sama sekali
2. BMasalah tak boleh dikendalikan tidak dapat diselesaikan oleh sebarang algoritma, manakala yang tak boleh diputuskan hanya memerlukan masa eksponen
3. CMasalah tak boleh diputuskan tiada algoritma untuk semua input; masalah tak boleh dikendalikan ada algoritma, tetapi terlalu perlahan
4. DMasalah tak boleh diputuskan berada dalam NP, manakala masalah tak boleh dikendalikan berada dalam P