Lembaran kerja Algoritma & kerumitan dengan jawapan

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²

Apakah yang diterangkan oleh masa larian kes purata?

1. ANilai tengah antara masa larian kes terbaik dan kes terburuk
2. BMasa untuk input dengan panjang purata
3. CMasa dijangka merentasi taburan input tertentu bersaiz n
4. DMasa pada komputer yang paling biasa

Apakah rekursi?

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

Anda mengisih tatasusunan n elemen sekali dan kemudian menjawab k pertanyaan keahlian dengan carian binari. Apakah jumlah kosnya?

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

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

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

Batas bawah bagi isihan berasaskan perbandingan dalam kes terburuk ialah:

1. AΩ(log n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(n)

Menggunakan teorem induk, T(n) = 8T(n/2) + O(n²) mempunyai penyelesaian:

1. AΘ(n²)
2. BΘ(n log n)
3. CΘ(n² log n)
4. DΘ(n³)

Algoritma pengaturcaraan dinamik Held–Karp menyelesaikan masalah jurujual kembara dengan tepat. Apakah masa larinya untuk n bandar?

1. AO(n!)
2. BO(n² 2ⁿ)
3. CO(n³)
4. DO(2^n²)