Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

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

Mengakses elemen array berdasarkan indeks memerlukan waktu:

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

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Apakah benar mengatakan bahwa algoritma O(n²) juga O(n³)?

1. AYa, tetapi hanya jika n lebih kecil dari 100
2. BTidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
3. CTidak, karena n³ lebih kecil daripada n² untuk n besar
4. DYa, karena Big O adalah batas atas dan n² tidak tumbuh lebih cepat daripada n³

Rekurens T(n) = 2T(n − 1) + O(1) menghasilkan apa?

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

Kompleksitas waktu Fibonacci rekursif naif (fib(n) = fib(n−1) + fib(n−2)) adalah:

1. AEksponensial
2. BLinear
3. CLogaritmik
4. DKonstan

Berapa waktu eksekusi algoritma Dijkstra dengan binary heap pada graf dengan V simpul dan E sisi?

1. AO(V + E)
2. BO(V³)
3. CO((V + E) log V)
4. DO(V × E)

Pernyataan mana tentang memilih elemen terkecil ke-k dari array tidak terurut yang benar?

1. AQuickselect berjalan dalam O(log n) pada kasus terburuk, karena hanya berekursi ke satu sisi pivot
2. BQuickselect berjalan dalam O(n) yang diharapkan, dan median-of-medians menjamin O(n) pada kasus terburuk
3. CSeleksi selalu memerlukan Ω(n log n) karena memerlukan pengurutan
4. DSeleksi hanya mungkin dilakukan dalam O(n²)