Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Berapa kompleksitas waktu kasus terbaik insertion sort, pada array yang sudah terurut?

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

Berapa kompleksitas waktu kasus terburuk merge sort?

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

Algoritma greedy:

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

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)

Sebuah fungsi menjalankan satu loop berisi n iterasi, lalu secara terpisah satu loop lain berisi n iterasi. Berapa kompleksitas waktunya?

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

Definisi kelas NP manakah yang benar?

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

Bagaimana travelling salesman problem diklasifikasikan?

1. AMasalah ini undecidable
2. BVersi keputusannya NP-complete dan versi optimasinya NP-hard
3. CVersi keputusannya di P tetapi versi optimasinya NP-complete
4. DMasalah ini berada di P karena algoritma Dijkstra menyelesaikannya dengan mengunjungi setiap kota satu kali