Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa kompleksitas waktu untuk mencari nilai terbesar dalam array tidak terurut berisi n bilangan?

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

Berapa kompleksitas waktu kasus terburuk insertion sort?

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

Suatu masalah biasanya disebut tractable jika:

1. AHanya dapat diselesaikan dengan mencoba setiap kemungkinan
2. BDapat diselesaikan dalam waktu konstan
3. CTidak memiliki solusi
4. DDapat diselesaikan dalam waktu polinomial

Batas bawah untuk pengurutan berbasis perbandingan pada kasus terburuk adalah:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Relasi rekurens T(n) = 2T(n/2) + O(n) memiliki solusi:

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

Mengapa dynamic programming tidak benar-benar mempercepat merge sort?

1. AMerge sort tidak memiliki struktur rekursif
2. BMerge sort sudah O(n)
3. CSubmasalahnya tidak tumpang tindih, sehingga tidak ada yang dapat dipakai ulang
4. DDynamic programming hanya bekerja pada masalah graf, bukan pada array

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

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

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

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