Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud base case pada fungsi rekursif?

1. ABaris pertama fungsi
2. BPemanggilan yang memakai memori paling banyak
3. CKasus dengan input terbesar, yang ditangani sebelum pemanggilan rekursif apa pun
4. DKasus yang dijawab langsung tanpa melakukan pemanggilan rekursif lagi

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar log₂ n
2. BSekitar n / 2
3. CSekitar n²
4. DSekitar n

Algoritma greedy:

1. AMengambil pilihan terbaik secara lokal pada setiap langkah
2. BSelalu memberikan solusi optimal
3. CHanya menggunakan rekursi
4. DMencoba setiap solusi yang mungkin

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)

Berapa kompleksitas waktu mengalikan dua matriks n × n dengan triple loop standar?

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

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

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

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

1. ABanyak kunci dapat bertabrakan (collision) di bucket yang sama
2. BAkses array memerlukan O(n)
3. CFungsi hash lambat
4. DKunci harus diurutkan terlebih dahulu