Lembar kerja Algoritma & kompleksitas dengan jawaban

Berapa waktu eksekusi counting sort untuk n bilangan bulat dalam rentang 0 sampai k?

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

Sebuah loop dimulai dengan i = 1 dan menggandakan i setiap iterasi sampai i > n. Berapa kali loop itu berjalan?

1. ASekitar n / 2
2. BSekitar n
3. CSekitar log₂ n
4. DSekitar n²

Apa yang digambarkan oleh waktu eksekusi kasus terburuk suatu algoritma?

1. AWaktu yang diperlukan pada komputer yang lambat
2. BWaktu yang diharapkan pada input acak berukuran n
3. CWaktu maksimum yang diperlukan atas semua input berukuran n
4. DWaktu yang diperlukan pada input terkecil

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

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

Berapa kompleksitas waktu teramortisasi (amortised) untuk menambahkan elemen ke array dinamis yang menggandakan kapasitasnya ketika penuh?

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

Apa artinya suatu masalah memiliki optimal substructure?

1. ASolusi optimal dapat dibangun dari solusi optimal submasalahnya
2. BMasalah itu memiliki tepat satu solusi optimal, yang dimiliki bersama oleh setiap submasalah
3. CMasalah itu dapat diselesaikan dalam waktu konstan
4. DSetiap submasalah memiliki ukuran yang sama

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

1. AAkses array memerlukan O(n)
2. BFungsi hash lambat
3. CBanyak kunci dapat bertabrakan (collision) di bucket yang sama
4. DKunci harus diurutkan terlebih dahulu

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. BPerbandingan pada node linked list lebih lambat
3. CBinary search memerlukan setidaknya dua kali lipat memori
4. DLinked list tidak dapat diurutkan