My first Magazine pemrograman-kompetitif-dasar | Page 91

8.1 Dynamic Array
II Sekilas Info JJ
Pada implementasinya, array A perlu dibuat menggunakan konsep pointer dan alokasi
memori.
Dengan cara ini, dynamic array dapat memperbesar ukurannya sesuai dengan banyaknya
elemen yang disimpan. Memori yang dibutuhkan paling banyak sebesar dua kali banyaknya
elemen yang disimpan.
Perhatikan bahwa operasi push kadang-kadang memerlukan proses yang tidak O(1). Hal ini
tidak seburuk kelihatannya. Sebab ketika dirata-rata, kompleksitas operasi push dapat dianggap
O(1).
Untuk lebih memahaminya, misalkan kita akan menyimpan N data pada sebuah dynamic array
kosong dengan melakukan N kali push . Dengan nilai awal maxSize = 1, diperlukan lipat ganda
ukuran array pada operasi push yang ke-2, 4, 8, 16, dan seterusnya sampai lebih besar atau
sama dengan N. Secara matematis, banyaknya operasi lipat ganda yang diperlukan adalah M,
dengan M = blog 2 Nc. Operasi lipat ganda ini dilakukan pada push yang ke-2 1 , 2 2 , 2 3 , ..., dan 2 M .
Untuk setiap lipat ganda pada push yang ke-x, diperlukan penyalinan data sebanyak x/2 elemen.
kan:
Banyaknya elemen yang disalin pada seluruh lipat ganda dapat dihitung dengan menjumlah-
2 1 2 2 2 3
2 M
+ + + ... +
2
2
2
2
Yang mana jumlahan ini dapat disederhanakan menjadi:
2 0 + 2 1 + 2 2 + ... + 2 M−1
Dengan rumus deret aritmetika, hasil jumlahan dari deret tersebut adalah 2 M − 1.
Perhatikan pula bahwa dipenuhi:
2 blog 2 Nc ≤ N
Mengingat M = blog 2 Nc, dipastikan 2 M − 1 tidak lebih dari N − 1.
Kini kita mengetahui bahwa total elemen yang disalin secara keseluruhan untuk push se-
banyak N kali tidak lebih dari N − 1. Selain penyalinan elemen, dilakukan pula penyimpanan
data pada setiap push . Misalkan setiap penyalinan elemen atau penyimpanan data pada push
dianggap membutuhkan 1 operasi. Artinya, banyaknya operasi maksimum untuk penyalinan
elemen ditambah penyimpanan data adalah N + N − 1 operasi. Ketika diambil rata-ratanya, setiap
push membutuhkan N+N−1
≈ 2 operasi. Dengan demikian, secara rata-rata push dapat dianggap
N
O(1).
81