Lembar kerja Algoritma & kompleksitas dengan jawaban

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

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

Berapa Big O dari 3n² + 5n + 2?

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

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

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

Dalam array terurut, Anda mencari dua elemen yang jumlahnya sama dengan target dengan menggerakkan satu pointer dari masing-masing ujung ke dalam. Berapa kompleksitas waktunya?

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

Apa yang diukur oleh analisis amortisasi?

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

Kira-kira berapa perbandingan yang diperlukan binary search pada kasus terburuk untuk array terurut berisi 1,000,000 elemen?

1. ASekitar 1,000
2. BSekitar 500,000
3. CSekitar 100
4. DSekitar 20

Mengapa pencarian rata-rata pada tabel hash adalah O(1) tetapi kasus terburuknya O(n)?

1. AKunci harus diurutkan terlebih dahulu
2. BAkses array memerlukan O(n)
3. CFungsi hash lambat
4. DBanyak kunci dapat bertabrakan (collision) di bucket yang sama

Dengan teorema master, T(n) = 8T(n/2) + O(n²) memiliki solusi:

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