My first Magazine pemrograman-kompetitif-dasar | Page 92

8 Struktur Data Dasar
II Sekilas Info JJ
Analisis kompleksitas untuk menghitung kompleksitas push disebut dengan amortized
analysis. Pada amortized analysis, kompleksitas suatu algoritma tidak semata-mata dinya-
takan menurut kasus terburuk yang mungkin, tetapi diperhatikan keseluruhan operasi yang
dilakukan. 12
Kompleksitas dari operasi push dynamic array lebih tepat untuk dikatakan amortized
O(1).
8.1.1
Aplikasi Dynamic Array
Struktur data ini cocok digunakan ketika kita tidak tahu banyaknya elemen yang akan disimpan.
Sebagai contoh, misalnya kita perlu menyimpan nama N orang yang dikelompokkan menurut
berat badan dalam kilogram (kg). Asumsikan pula berat badan N orang ini berupa bilangan bulat
pada rentang 1 kg sampai dengan K kg, dan belum diketahui berapa paling banyak orang yang
memiliki berat sekian kg.
Untuk menyimpan data tersebut, kita dapat membuat array nama dengan K elemen, yang
masing-masing elemennya berupa dynamic array . Untuk orang dengan berat x kg, simpan datanya
pada dynamic array nama[x]. Dengan cara ini, kebutuhan memorinya adalah O(N).
Bandingkan apabila kita membuat array nama dengan K elemen, yang masing-masing ele-
mennya berupa array . Berhubung untuk kasus paling buruk terdapat N orang yang memiliki berat
yang sama, maka kita perlu membuat masing-masing array sebesar N. Kebutuhan memorinya
adalah O(KN), yang jelas tidak efisien apabila K cukup besar.
Contoh ini merupakan salah satu penggunaan dari dynamic array . Seiring dengan pembela-
jaran dan latihan, Anda akan menemukan kasus-kasus ketika dynamic array diperlukan.
8.1.2
Implementasi Dynamic Array
Implementasi dynamic array dapat diwujudkan dengan sebuah array , variabel size, dan
maxSize. Operasi untuk mengubah atau mengakses elemen dari suatu indeks dapat langsung
dilakukan pada A. Tentu saja indeks yang perlu diakses harus kurang dari maxSize. Perhatikan
Algoritma 40 untuk memahami operasi push pada dynamic array .
Algoritma 40 Implementasi dynamic array .
procedure INITIALIZE D YNAMIC A RRAY () . Seluruh variabel yang diinisialisasi bersifat global
size ← 0
3:
maxSize ← 1
4:
A ← new integer[maxSize]
5: end procedure
1:
2:
82