Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang berjalan di banyak prosesor
2. BAlgoritma yang menebak jawaban secara acak
3. CAlgoritma yang selalu memakai rekursi
4. DAlgoritma yang mencoba semua kandidat solusi yang mungkin

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

Apa yang dimaksud dengan algoritma?

1. ABahasa pemrograman yang dirancang untuk menulis rumus matematika
2. BStruktur data yang menyimpan bilangan
3. CSetiap program komputer yang memiliki antarmuka grafis
4. DUrutan langkah yang terdefinisi dengan baik dan berhingga untuk menyelesaikan suatu masalah

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 20
2. BSekitar 100
3. CSekitar 500,000
4. DSekitar 1,000

Dengan koin 1, 3, dan 4 serta jumlah 6, berapa koin yang dipakai metode greedy "koin terbesar dulu" dibandingkan solusi optimal?

1. AGreedy memakai 4 koin; optimalnya 3
2. BGreedy memakai 2 koin; optimalnya 2
3. CGreedy memakai 3 koin; optimalnya 2
4. DGreedy memakai 3 koin; optimalnya 3

Pernyataan manakah tentang P dan NP yang benar?

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

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. APerbandingan pada node linked list lebih lambat
2. BMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung
3. CLinked list tidak dapat diurutkan
4. DBinary search memerlukan setidaknya dua kali lipat memori