Lembar kerja Algoritma & kompleksitas dengan jawaban

Apa syarat binary search terhadap inputnya?

1. AArray tidak boleh berisi lebih dari 1000 elemen
2. BPanjang array harus pangkat dua
3. CArray hanya boleh berisi bilangan positif
4. DArray harus terurut

Apa yang dimaksud dengan algoritma brute force?

1. AAlgoritma yang menebak jawaban secara acak
2. BAlgoritma yang selalu memakai rekursi
3. CAlgoritma yang mencoba semua kandidat solusi yang mungkin
4. DAlgoritma yang berjalan di banyak prosesor

Strategi desain apa yang digunakan merge sort?

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

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

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

Berapa kompleksitas waktu kasus terburuk quicksort?

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

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

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

Untuk menunjukkan bahwa masalah baru X adalah NP-hard, apa yang harus Anda lakukan?

1. AMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
2. BMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
3. CMereduksi X ke masalah NP-hard yang sudah dikenal dalam waktu polinomial
4. DMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil

Definisi kelas NP manakah yang benar?

1. AMasalah yang tidak polinomial
2. BMasalah keputusan yang jawaban "ya"-nya dapat diverifikasi dalam waktu polinomial jika diberi sertifikat
3. CMasalah yang tidak dapat diselesaikan dalam waktu polinomial
4. DMasalah yang tidak dapat diselesaikan algoritma apa pun