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(E log V)
3. CO(V × E)
4. DO(V²)

Algoritma O(n) memerlukan 3 detik untuk n = 1 juta. Kira-kira berapa lama untuk n = 2 juta?

1. A6 detik
2. B3 detik
3. C12 detik
4. D9 detik

Apa yang digambarkan oleh waktu eksekusi kasus rata-rata?

1. ANilai tengah antara waktu eksekusi kasus terbaik dan kasus terburuk
2. BWaktu pada komputer yang paling umum
3. CWaktu untuk input dengan panjang rata-rata
4. DWaktu yang diharapkan atas distribusi input berukuran n tertentu

Anda mengurutkan array berisi n elemen sekali, lalu menjawab k kueri keanggotaan dengan binary search. Berapa total biayanya?

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

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

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(n)
2. BO(log n)
3. CO(n log n)
4. DO(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. BMenunjukkan bahwa X dapat diverifikasi dalam waktu polinomial
3. CMereduksi masalah NP-hard yang sudah dikenal ke X dalam waktu polinomial
4. DMenunjukkan bahwa X tidak memiliki algoritma polinomial untuk input kecil

Mengapa binary search tidak menghasilkan waktu O(log n) pada singly linked list?

1. AMencapai elemen tengah memerlukan O(n) langkah, karena tidak ada akses indeks langsung
2. BBinary search memerlukan setidaknya dua kali lipat memori
3. CPerbandingan pada node linked list lebih lambat
4. DLinked list tidak dapat diurutkan