Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa Big O dari 3n² + 5n + 2?

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

Apa yang dimaksud dengan algoritma brute force?

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

Manakah dari waktu eksekusi berikut yang polinomial?

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

Pemrograman dinamis (dynamic programming) berguna ketika suatu masalah memiliki:

1. ATidak ada submasalah sama sekali, sehingga dapat diselesaikan dalam satu langkah
2. BSubmasalah yang tumpang tindih dan substruktur optimal
3. CHanya input acak
4. DSatu loop saja

Algoritma manakah yang menemukan lintasan terpendek dari satu sumber pada graf dengan bobot sisi non-negatif?

1. ABellman–Ford diperlukan dalam semua kasus
2. BDepth-first search (DFS)
3. CAlgoritma Kruskal
4. DAlgoritma Dijkstra

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

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

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

Dua hal apa yang harus ditunjukkan untuk membuktikan bahwa masalah keputusan X adalah NP-complete?

1. AX tidak memiliki algoritma polinomial, dan X decidable
2. BX berada di NP, dan masalah NP-complete yang sudah dikenal dapat direduksi ke X dalam waktu polinomial
3. CX berada di P, dan X dapat direduksi ke SAT
4. DX dapat direduksi ke masalah di P, dan X berada di NP