Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Notasi manakah yang menyatakan batas atas (upper bound) pertumbuhan?

1. ALittle omega
2. BBig O
3. CBig Omega
4. DBig Theta

Apa tiga langkah algoritma divide and conquer?

1. ABaca, hitung, tulis
2. BTebak, periksa, ulangi
3. CDivide, conquer, combine (bagi, taklukkan, gabungkan)
4. DUrutkan, cari, kembalikan

Algoritma greedy:

1. ASelalu memberikan solusi optimal
2. BHanya menggunakan rekursi
3. CMencoba setiap solusi yang mungkin
4. DMengambil pilihan terbaik secara lokal pada setiap langkah

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

1. ALinear
2. BEksponensial
3. CLogaritmik
4. DKonstan

Apa yang diukur oleh analisis amortisasi?

1. ABiaya rata-rata per operasi atas urutan operasi kasus terburuk
2. BBiaya algoritma pada input terbaik
3. CBiaya yang diharapkan atas input acak
4. DBiaya satu operasi yang paling mahal di mana pun dalam urutan itu

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

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

Berapa kompleksitas waktu membangun binary heap dari n elemen tidak terurut dengan metode bottom-up?

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