Fondasi · Pelajaran 2 dari 10
Array dan array dinamis
9 menit baca · BelajarCode
Array menyimpan elemen berdampingan di memori. Karena posisinya bisa dihitung langsung (alamat awal + i × ukuran elemen), akses ke indeks mana pun O(1). Kelemahannya, ukuran array tetap.
Array dinamis mengatasi ini: jika penuh, ia meminta memori baru yang lebih besar (biasanya dua kali lipat), menyalin semua elemen, lalu membuang yang lama. List di Python dan ArrayList di Java bekerja dengan cara ini.
1class ArrayDinamis:2 def __init__(self):3 self.kapasitas = 14 self.banyak = 05 self.data = [None] * self.kapasitas6 self.salinan = 078 def tambah(self, nilai):9 if self.banyak == self.kapasitas:10 self._perbesar()11 self.data[self.banyak] = nilai12 self.banyak += 11314 def _perbesar(self):15 baru = [None] * (self.kapasitas * 2)16 for i in range(self.banyak):17 baru[i] = self.data[i]18 self.salinan += 119 self.data = baru20 self.kapasitas *= 22122 def ambil(self, i):23 if not 0 <= i < self.banyak:24 raise IndexError("indeks di luar batas")25 return self.data[i]262728arr = ArrayDinamis()29for x in range(1000):30 arr.tambah(x)31print("Banyak:", arr.banyak, "Kapasitas:", arr.kapasitas)32print("Total penyalinan:", arr.salinan)33print("Rata-rata penyalinan per tambah:", arr.salinan / arr.banyak)34print("Elemen ke-500:", arr.ambil(500))Banyak: 1000 Kapasitas: 1024 Total penyalinan: 1023 Rata-rata penyalinan per tambah: 1.023 Elemen ke-500: 500
Biaya teramortisasi
Walaupun sesekali satu operasi tambah mahal (harus menyalin semua elemen), totalnya tetap kecil: 1 + 2 + 4 + ... + 512 = 1023 penyalinan untuk 1000 penambahan. Rata-ratanya sekitar satu penyalinan per penambahan, sehingga tambah disebut O(1) teramortisasi.
Jika kapasitas hanya ditambah sedikit demi sedikit (misalnya +10), total penyalinan menjadi kuadratik. Menggandakan kapasitas adalah kunci efisiensinya.
Menyisipkan di tengah itu mahal
1def sisipkan(daftar, posisi, nilai):2 geser = 03 daftar.append(None)4 for i in range(len(daftar) - 1, posisi, -1):5 daftar[i] = daftar[i - 1]6 geser += 17 daftar[posisi] = nilai8 return geser910data = list(range(10))11print("Geser saat menyisip di awal:", sisipkan(data, 0, -1))12print("Geser saat menyisip di akhir:", sisipkan(data, len(data) - 1, 99))13print(data)Geser saat menyisip di awal: 10 Geser saat menyisip di akhir: 1 [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 99, 9]
Menyisip di awal menggeser semua elemen ke kanan, jadi O(n). Inilah alasan list.insert(0, x) dan list.pop(0) di Python lambat untuk list yang panjang.
Cek pemahaman
Kenapa menambah elemen di akhir array dinamis disebut O(1) teramortisasi, padahal kadang harus menyalin semua elemen?
Latihan
Hapus dari belakang dan menyusutkan
Tambahkan metode hapus_akhir() ke ArrayDinamis yang mengembalikan elemen terakhir. Jika banyak elemen tinggal seperempat kapasitas, kapasitas diperkecil menjadi setengahnya.
Pembahasan
1class ArrayDinamis:2 def __init__(self):3 self.kapasitas = 14 self.banyak = 05 self.data = [None]67 def _ubah_kapasitas(self, baru):8 data_baru = [None] * baru9 for i in range(self.banyak):10 data_baru[i] = self.data[i]11 self.data = data_baru12 self.kapasitas = baru1314 def tambah(self, nilai):15 if self.banyak == self.kapasitas:16 self._ubah_kapasitas(self.kapasitas * 2)17 self.data[self.banyak] = nilai18 self.banyak += 11920 def hapus_akhir(self):21 if self.banyak == 0:22 raise IndexError("array kosong")23 self.banyak -= 124 nilai = self.data[self.banyak]25 self.data[self.banyak] = None26 if self.kapasitas > 1 and self.banyak <= self.kapasitas // 4:27 self._ubah_kapasitas(self.kapasitas // 2)28 return nilai293031arr = ArrayDinamis()32for x in range(16):33 arr.tambah(x)34print("Kapasitas setelah 16 tambah:", arr.kapasitas)35for _ in range(13):36 arr.hapus_akhir()37print("Banyak:", arr.banyak, "Kapasitas:", arr.kapasitas)Kapasitas setelah 16 tambah: 16 Banyak: 3 Kapasitas: 8
Menyusut saat tinggal seperempat, bukan setengah, mencegah kapasitas naik turun terus jika elemen ditambah dan dihapus bergantian tepat di batas.
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.