Lembar kerja Algoritma & kompleksitas dengan jawaban

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar log₂ n
2. BSekitar n / 2
3. CSekitar n
4. DSekitar n²

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada komputer yang lambat
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu maksimum yang diperlukan atas semua input berukuran n
4. DWaktu yang diperlukan pada input terkecil

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Quicksort selalu memakai elemen pertama sebagai pivot. Pada input mana algoritma ini menunjukkan perilaku kasus terburuknya?

1. AArray dengan panjang 2
2. BArray dalam urutan acak
3. CArray yang sudah terurut
4. DArray yang semua elemennya berbeda

Apa yang dihitung algoritma Floyd–Warshall, dan seberapa cepat?

1. ALintasan terpendek dari satu simpul sumber ke semua simpul lain dalam O(V + E)
2. BUrutan topologis dalam O(V²)
3. CLintasan terpendek antara semua pasangan simpul dalam O(V³)
4. DMinimum spanning tree dalam O(E log V)

Mengapa algoritma Dijkstra dapat memberikan hasil yang salah ketika sebagian bobot sisi negatif?

1. AAlgoritma itu masuk ke loop tak hingga pada setiap sisi negatif
2. BBilangan negatif tidak dapat disimpan dalam priority queue
3. CAlgoritma itu hanya bekerja pada graf tak berarah
4. DSimpul ditetapkan final saat diekstraksi, tetapi sisi negatif berikutnya masih dapat memberinya lintasan yang lebih pendek

Apa perbedaan antara masalah undecidable dan masalah intractable?

1. AKeduanya berarti masalah itu sama sekali tidak memiliki algoritma
2. BMasalah intractable tidak dapat diselesaikan oleh algoritma apa pun, sedangkan masalah undecidable hanya memerlukan waktu eksponensial
3. CMasalah undecidable berada di NP, sedangkan masalah intractable di P
4. DTidak ada algoritma yang menyelesaikan masalah undecidable untuk semua input, sedangkan masalah intractable dapat diselesaikan tetapi terlalu lambat