Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Berapa kompleksitas waktu depth-first search pada graf yang disimpan sebagai adjacency list?

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

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

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

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

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

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(nk)
4. DO(k n log n)

Berapa kompleksitas waktu algoritma dynamic programming standar untuk longest common subsequence dari string dengan panjang m dan n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. ABinary search memerlukan setidaknya dua kali lipat memori
2. BPerbandingan pada node linked list lebih lambat
3. CLinked list tidak dapat diurutkan
4. DMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung

Apa yang ditetapkan oleh teorema Cook–Levin?

1. ASetiap masalah NP dapat diselesaikan dalam waktu eksponensial
2. BBoolean satisfiability problem (SAT) adalah NP-complete
3. CHalting problem tidak dapat diputuskan (undecidable)
4. DP tidak sama dengan NP