Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

1. ADapat diselesaikan dalam waktu konstan
2. BTidak memiliki solusi
3. CHanya dapat diselesaikan dengan mencoba setiap kemungkinan
4. DDapat diselesaikan dalam waktu polinomial

Waktu eksekusi suatu algoritma adalah O(n). Pertumbuhan ini disebut apa?

1. ALinear
2. BKonstan
3. CLogaritmik
4. DKuadratik

Kelas kompleksitas manakah yang tumbuh paling cepat untuk n yang besar?

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

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

Berapa kompleksitas waktu kasus terburuk quicksort?

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

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

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

Lintasan sederhana terpendek dapat ditemukan dalam waktu polinomial. Apa yang diketahui tentang mencari lintasan sederhana terpanjang antara dua simpul pada graf umum?

1. ASelalu dapat diselesaikan dalam O(V + E)
2. BMasalah itu NP-hard
3. CMasalah itu undecidable
4. DDapat diselesaikan dengan algoritma Dijkstra memakai bobot yang dinegasikan

Pernyataan manakah tentang P dan NP yang benar?

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