Kuis 3 - ASD (B)

Suatu algoritma membandingkan elemen pertama dari sebuah array dengan seluruh elemen lainnya satu per satu. Jika array berisi n elemen, algoritma tersebut melakukan paling banyak n – 1 perbandingan. Notasi Big O manakah yang paling tepat untuk menggambarkan kompleksitas waktu dari algoritma tersebut?

• O(n – 1), tetapi disederhanakan menjadi O(n) seiring bertambahnya n

• O(1) – karena hanya satu kali perbandingan dilakukan

• O(log n) – karena jumlah perbandingan tumbuh secara logaritmik

• O(n²) – karena setiap elemen dibandingkan dengan semua elemen lainnya

Berdasarkan grafik dan penjelasan pada gambar, apa yang terjadi terhadap waktu eksekusi (runtime) jika ukuran input n dilipatgandakan dalam algoritma dengan kompleksitas waktu O(n²)?

• Runtime akan tetap sama karena pertambahan input tidak memengaruhi jumlah operasi

• Runtime akan bertambah dua kali lipat karena hanya ada dua kali lebih banyak data

• Runtime akan bertambah empat kali lipat karena waktu eksekusi tumbuh secara kuadratik terhadap n

• Runtime akan meningkat secara linear seiring dengan pertambahan ukuran input

Sebuah array berisi nilai:

[10, 50, 30, 70, 80, 60, 20, 90, 40]

Jika kita menggunakan algoritma linear search untuk mencari nilai 20, berapa jumlah perbandingan yang diperlukan hingga elemen tersebut ditemukan?

• 4

• 5

• 7

• 9

Berapa banyak perbandingan yang dilakukan oleh algoritma pencarian linier tersebut jika elemen yang dicari x berada di posisi terakhir dalam array dengan panjang n?

• 1 perbandingan

• n − 1 perbandingan

• O(log n) perbandingan

• n perbandingan

Dalam algoritma pencarian linier, pernyataan berikut benar, kecuali:

• Kompleksitas waktu pada kasus terbaik adalah O(1), karena elemen langsung ditemukan di indeks pertama.

• Kompleksitas waktu pada kasus rata-rata adalah O(n/2), karena rata-rata pencarian dilakukan hingga setengah elemen.

• Kompleksitas waktu pada kasus terburuk adalah O(n), ketika elemen tidak ditemukan atau berada di indeks terakhir.

• Dalam semua kasus, jumlah perbandingan maksimal yang dilakukan tidak akan melebihi n.

Diberikan array terurut menaik berikut:

[2, 5, 8, 12, 16, 23, 38, 56, 72, 91] dan nilai yang ingin dicari adalah 23. Menggunakan algoritma Binary Search, berapa jumlah maksimum perbandingan yang dilakukan hingga elemen 23 ditemukan?

• 1

• 2

• 3

• 4

Mengapa algoritma Binary Search jauh lebih efisien dibandingkan Linear Search dalam kasus pencarian pada array yang sudah terurut?

• Karena Binary Search selalu menemukan elemen dalam satu langkah

• Karena Binary Search hanya cocok digunakan pada array dengan ukuran genap

• Karena Binary Search mengeliminasi separuh dari elemen yang dicari setiap kali perbandingan dilakukan

• Karena Binary Search mengurutkan elemen terlebih dahulu sebelum melakukan pencarian

Diberikan array berikut:

[8, 22, 7, 9, 31, 5, 13]

Jika array tersebut diurutkan dalam urutan naik (ascending) menggunakan algoritma Bubble Sort standar tanpa optimasi (selalu melakukan iterasi penuh meskipun sudah terurut sebagian), maka berapa banyak pertukaran (swapping) yang dilakukan hingga array benar-benar terurut?

• 11

• 12

• 13

• 10

Dalam proses kerja algoritma Selection Sort, manakah pernyataan berikut yang paling tepat menggambarkan bagaimana elemen-elemen dipindahkan dalam array?

• Setiap elemen dibandingkan dengan semua elemen di depannya dan ditukar jika lebih besar

• Elemen maksimum dipindahkan ke bagian akhir pada setiap iterasi

• Elemen minimum dari bagian tak terurut dipilih dan ditukar ke posisi awal dari bagian tak terurut

• Elemen pertama dibandingkan langsung dengan elemen terakhir dan ditukar jika perlu

Apa jenis algoritma pengurutan yang diimplementasikan pada kode di atas?

• Selection Sort

• Insertion Sort

• Bubble Sort

• Merge Sort