Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu binary search pada array yang sudah terurut?

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

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

1. ALogaritmik
2. BKonstan
3. CLinear
4. DKuadratik

Suatu masalah biasanya disebut tractable jika:

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

Apa yang diukur oleh analisis amortisasi?

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

Berapa kompleksitas waktu dari: for i = 1 to n: for j = 1 to i: lakukan kerja O(1)?

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

Mengapa banyak rutin pengurutan pustaka beralih ke insertion sort untuk subarray yang sangat kecil?

1. AAlgoritma rekursif tidak dapat menangani array di bawah 10 elemen
2. BInsertion sort adalah O(n log n) pada kasus terburuk
3. CInsertion sort memakai memori lebih sedikit daripada algoritma pengurutan lain untuk input besar
4. DInsertion sort memiliki overhead kecil dan cepat pada input kecil atau hampir terurut

Manakah dari masalah satisfiability berikut yang diketahui dapat diselesaikan dalam waktu polinomial?

1. A2-SAT, dengan setiap klausa berisi paling banyak dua literal
2. B3-SAT, dengan setiap klausa berisi tepat tiga literal
3. CSAT umum pada formula dalam bentuk normal konjungtif
4. DCircuit satisfiability

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

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