Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Manakah dari waktu eksekusi berikut yang polinomial?

1. AO(2ⁿ)
2. BO(nⁿ)
3. CO(n!)
4. DO(n³)

Suatu masalah biasanya disebut tractable jika:

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

Apa yang diukur oleh analisis amortisasi?

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

Berapa waktu eksekusi LSD radix sort pada n bilangan bulat dengan d digit dalam basis k?

1. AO(n log n)
2. BO(n²)
3. CO(dn log k)
4. DO(d(n + k))

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 log n)
3. CO(mn)
4. DO(m + n)

Berapa biaya waktu dan ruang untuk menghitung bilangan Fibonacci ke-n dengan loop yang hanya menyimpan dua nilai terakhir?

1. AWaktu O(n) dan ruang O(1)
2. BWaktu O(2ⁿ) dan ruang O(1)
3. CWaktu O(log n) dan ruang O(n)
4. DWaktu O(n) dan ruang O(n)

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

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