Sunday, 28 May 2017

Struktur Data Sparse Table

Kali ini saya membahas tentang struktur data yang menurut saya jarang diajarkan secara formal. Selama ini saya mempelajarinya sebagai bagian dari suatu algoritma lebih besar, seperti pencarian LCA (Lowest Common Ancestor) atau RMQ (Range Minimum Query).


Permasalahan Motivasi

Terdapat N orang di sebuah ruangan. Terdapat sebuah bola panas, yang awalnya diberikan pada seseorang. Ketika orang ke-i menerima bola panas ini, ia akan mengoper bola panas itu ke orang ke-p[i]. Proses menerima bola dan mengopernya terjadi dalam satu periode yang disebut satu putaran.

Kemudian Anda diberikan banyak pertanyaan berbunyi:
Ditentukan suatu angka X dan Y. Bila awalnya orang yang menerima bola panas adalah orang ke-X, maka dalam Y putaran berikutnya, di mana bola panas itu berada?

Asumsikan X dan Y tidak lebih dari N.

Thursday, 25 May 2017

Amortized Analysis

Jika Anda belajar library bernama "vector" di C++, maka mungkin Anda pernah mendengar bahwa kompleksitas push_back adalah amortized O(1). Apa yang dimaksud dengan amortized?

Penerjemahan langsung ke Bahasa Indonesia agak lucu, yaitu "dilunasi dengan angsuran". Untuk lebih memahaminya, lebih baik kita membahas contoh soalnya, yaitu push_back pada vector.

Permasalahan

Anda ingin membuat array, tetapi tidak mengetahui banyaknya elemen maksimal yang mungkin ditampung dalam suatu waktu. Salah satu cara yang dapat dilakukan adalah menggunakan "resize-able array".

Pertama mulai dengan sebuah array yang maksimal dapat menampung X elemen. Misalkan X kita beri nilai 10. Operasi menambahkan elemen di paling belakang awalnya array dapat dilakukan dengan cara kira-kira seperti ini: