Lembar kerja Algoritma & kompleksitas dengan jawaban

Manakah yang tumbuh paling lambat ketika n menjadi besar?

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

Apa yang dimaksud dengan memoisasi?

1. AMenulis komentar di samping setiap baris kode
2. BMengubah rekursi menjadi loop yang setara secara otomatis sehingga call stack tidak diperlukan
3. CMenyimpan hasil pemanggilan fungsi agar pemanggilan berulang dijawab dari memori
4. DMembebaskan memori setelah fungsi selesai

Apa tiga langkah algoritma divide and conquer?

1. ATebak, periksa, ulangi
2. BDivide, conquer, combine (bagi, taklukkan, gabungkan)
3. CUrutkan, cari, kembalikan
4. DBaca, hitung, tulis

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

Pada activity selection problem, aturan greedy mana yang selalu menghasilkan jumlah maksimum aktivitas yang tidak saling tumpang tindih?

1. APilih aktivitas yang selesai paling awal, lalu ulangi dengan aktivitas yang kompatibel
2. BPilih aktivitas terpendek terlebih dahulu
3. CPilih aktivitas yang dimulai paling awal
4. DPilih aktivitas dengan tumpang tindih paling sedikit terlebih dahulu, lalu ulangi dengan aktivitas yang kompatibel

Pernyataan manakah tentang P dan NP yang benar?

1. ATelah dibuktikan bahwa P ≠ NP
2. BMasalah NP tidak dapat diverifikasi dengan cepat
3. CNP berarti "not polynomial"
4. DSetiap masalah di P juga termasuk dalam NP

Insertion sort berjalan dalam O(n) pada input terurut. Apakah ini bertentangan dengan batas bawah Ω(n log n) untuk pengurutan berbasis perbandingan?

1. AYa, tetapi hanya untuk array yang lebih pendek dari 100
2. BTidak, karena insertion sort bukan pengurutan berbasis perbandingan
3. CYa, sehingga batas bawah itu salah
4. DTidak, batas bawah itu berlaku untuk kasus terburuk atas semua input, bukan untuk setiap input