Lembar kerja Algoritma & kompleksitas dengan jawaban

Suatu masalah biasanya disebut tractable jika:

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

Strategi desain apa yang digunakan merge sort?

1. ADivide and conquer (bagi dan taklukkan)
2. BPilihan greedy
3. CBrute force
4. DDynamic programming

Apa arti f(n) = Θ(g(n))?

1. Af tumbuh benar-benar lebih cepat daripada g
2. Bf tumbuh benar-benar lebih lambat daripada g
3. Cf tumbuh dengan laju yang sama dengan g, dibatasi di atas dan di bawah oleh kelipatan konstan g
4. Df selalu lebih kecil daripada g untuk setiap n, sehingga g membatasinya dari atas tetapi tidak pernah dari bawah

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

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

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

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

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

1. ATidak, karena Big O harus selalu menyatakan laju pertumbuhan yang tepat dari fungsi itu
2. BYa, tetapi hanya jika n lebih kecil dari 100
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³

Mengapa setiap pencarian berbasis perbandingan dalam array terurut memerlukan Ω(log n) perbandingan pada kasus terburuk?

1. ABinary search adalah satu-satunya algoritma yang mungkin, dan memerlukan log₂ n perbandingan
2. BSetiap perbandingan memerlukan waktu logaritmik
3. CSetiap elemen harus dibandingkan setidaknya sekali
4. DPohon keputusan dengan n kemungkinan hasil harus memiliki kedalaman setidaknya log₂ n

Masalah penghentian (halting problem) menunjukkan bahwa:

1. ASetiap program pada akhirnya akan berhenti
2. BTidak ada algoritma yang dapat memutuskan untuk setiap program dan input apakah program tersebut akan berhenti
3. CBeberapa program berjalan lebih cepat di komputer yang lebih cepat, sehingga berhenti atau tidaknya bergantung pada perangkat keras
4. DLoop sebaiknya dihindari