Lembaran kerja Algoritma & kerumitan dengan jawapan

Bagaimanakah isihan pemilihan berfungsi?

1. AIa berulang kali mencari minimum bahagian tidak tersusun dan menukarnya ke hadapan
2. BIa berulang kali menukar elemen jiran yang berada dalam susunan salah
3. CIa membahagikan tatasusunan kepada dua dan mencantumkannya
4. DIa menyisipkan setiap elemen ke dalam bahagian tersusun yang berkembang dengan menganjak

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

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

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

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

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

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

Apakah kerumitan masa bagi: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Kerumitan masa Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) ialah:

1. AEksponen
2. BMalar
3. CLogaritma
4. DLinear

Bagaimanakah masalah jurujual kembara dikelaskan?

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

Masalah galas 0/1 yang diselesaikan dengan pengaturcaraan dinamik mengambil masa O(nW). Mengapakah ini dipanggil pseudo-polinomial?

1. AKerana algoritma itu dirawakkan dan masa larinya berbeza-beza bagi setiap input
2. BKerana ia hanya berfungsi untuk W = 0
3. CW ialah satu nombor, jadi masanya eksponen dalam bilangan bit yang digunakan untuk menulis W
4. DKerana n sentiasa kecil