kami tidak dapat mengelompokkan tipe data yang berbeda dalam larik. Seperti, kombinasi integer dan char, char dan float dll
Oleh karena itu array disebut sebagai tipe data homogen
Contoh
int arr[5]={10,20,30,40,50};
Indeks Larik
Dengan menggunakan nilai indeks, kita dapat langsung mengakses elemen yang diinginkan dalam array
Indeks array dimulai dari 0, bukan 1
Untuk mengakses elemen pertama, kita bisa langsung menggunakan indeks 0. saya. dan usia[0]
Untuk mengakses elemen ke-5, kita bisa langsung menggunakan indeks 4. saya. dan usia[4]
Kita dapat memanipulasi elemen ke-N dengan menggunakan indeks N - 1. {Di mana N > 0}
Secara umum, array berukuran N akan memiliki elemen dari indeks 0 hingga N-1
Mengakses elemen array menggunakan index
/* * Accessing array elements using index */ #include int main() { int arr[5] = {10, 20, 30, 40, 50}; //printing 3rd element which is index 2 printf("3rd element = %d\n", arr[2]); //printing 5th element which is index 4 printf("5th element = %d\n", arr[4]); return 0; } _
Analisis kompleksitas waktu
Menggunakan nilai indeks, kita dapat mengakses elemen array dalam waktu yang konstan
Jadi kompleksitas waktu adalah O(1) untuk mengakses elemen dalam array
Topik yang Mungkin Anda Suka
Kode daftar yang tidak efisien secara tidak sengaja sangat umum terjadi dan sulit ditemukan, tetapi ketika daftar bertambah, kode Anda terhenti
Teks ini melihat secara mendetail kinerja operasi larik dasar dan membahas alternatif dari larik standar. Ini juga mencakup lembar contekan dari operasi daftar mahal di Java dan Python
Dasar-dasar susunan
Array adalah tipe data koleksi yang paling mendasar. Ini terdiri dari elemen-elemen dari satu jenis yang ditata secara berurutan dalam memori. Anda dapat mengakses elemen apa pun dalam waktu yang konstan dengan pengindeksan bilangan bulat
Array tersedia dalam semua bahasa utama. Di Java, Anda dapat menggunakan notasi []_, atau kelas ArrayList yang lebih ekspresif. Di Python, tipe data daftar diimplementasikan sebagai array
Pertunjukan
Secara umum, array memiliki kinerja yang sangat baik. Mengoptimalkan performa array adalah tujuan utama desain hardware memori dan pengelolaan memori OS
- Anda dapat membaca atau menulis item daftar dengan mengacu pada indeksnya di
- Namun, beberapa operasi array – seperti tambah, hapus, dan cari – bisa sangat mahal, dengan kasus terburuk
Susunan dinamis
Dalam larik dinamis, elemen disimpan di awal larik tetap yang mendasarinya, dan posisi yang tersisa tidak digunakan
- Jika masih ada ruang tersisa, elemen dapat ditambahkan di bagian akhir dalam waktu yang konstan
- Jika tidak ada posisi yang tersisa, array berukuran tetap yang mendasarinya perlu ditingkatkan ukurannya
Berikut tampilan memori saat menambahkan elemen 2, 7, 1, 3, 8, 4 ke array dinamis yang awalnya kosong dengan kapasitas 2
Waktu untuk menambahkan elemen adalah linier dalam kasus terburuk, karena melibatkan pengalokasian memori baru dan penyalinan setiap elemen
Namun, jika kita memperluas array dengan proporsi konstan, mis. g. dengan menggandakan ukurannya, total waktu untuk menyisipkan n elemen akan menjadi O(n), dan kita katakan bahwa setiap penyisipan memerlukan waktu diamortisasi yang konstan
Lihat Kompleksitas waktu diamortisasi untuk informasi lebih lanjut tentang cara menganalisis struktur data yang memiliki operasi mahal yang jarang terjadi
Operasi daftar mahal
Untuk menambah atau menghapus elemen pada indeks tertentu bisa mahal, karena semua elemen setelah indeks harus digeser. Kompleksitas waktu terburuk adalah linier
Demikian pula, mencari elemen untuk suatu elemen bisa jadi mahal, karena Anda mungkin perlu memindai seluruh larik
Dalam contoh kode Python ini, panggilan pop(0) waktu linier, yang menghapus elemen pertama daftar, menyebabkan kode yang sangat tidak efisien
Peringatan. Kode ini memiliki. Ini berjalan dalam waktu Θ(n2), dengan n adalah panjang awal daftar a. Ini berarti program hanya berguna untuk daftar pendek, dengan paling banyak beberapa ribu elemen
while len(a) > 0: foo = a.pop(0)
Untuk menghindari jenis masalah kinerja ini, Anda perlu mengetahui perbedaan antara operasi daftar waktu konstan dan linier
Metode Java ArrayList yang mahal
Metode ArrayList berikut beroperasi pada subkumpulan elemen, tetapi masih memiliki kerumitan waktu yang bergantung pada ukuran n dari daftar
MethodWorst-case timeadd(int i, E element)n - iremove(int i)n - i[]0n - i[]2n[]4n[]6n[]8nCatatan. ArrayList0 membutuhkan waktu diamortisasi konstan, meskipun waktu terburuknya adalah linear
Operasi daftar Python mahal
Operasi daftar Python berikut beroperasi pada subset elemen, tetapi masih memiliki kerumitan waktu yang bergantung pada ArrayList1
Catatan. pop(0)4 membutuhkan waktu diamortisasi yang konstan, meskipun waktu terburuknya adalah linier
Alternatif
Tidak ada struktur data lain yang dapat bersaing dengan efisiensi pengindeksan array dan iterasi array. Namun, Anda mungkin perlu mengambil pendekatan berbeda jika operasi lain sangat penting untuk performa
Peta dan kamus
Tabel hash, sering kali dalam bentuk peta atau kamus, adalah alternatif yang paling umum digunakan untuk array. Ini mengimplementasikan kumpulan pasangan kunci-nilai yang tidak diurutkan, di mana setiap kunci unik
- Tabel hash menawarkan kombinasi operasi pencarian, tambah, dan hapus yang efisien
- Semua operasi ini berjalan dalam waktu konstan yang diharapkan. Kompleksitas waktu untuk operasi penambahan diamortisasi
Di Jawa, tabel hash adalah bagian dari perpustakaan standar (HashSet dan HashMap). Banyak bahasa modern, seperti Python dan Go, memiliki kamus dan peta bawaan yang diimplementasikan oleh tabel hash
Array yang diurutkan
Jika pencarian penting untuk kinerja, Anda mungkin ingin menggunakan larik yang diurutkan
- Dalam larik terurut, Anda dapat menggunakan pencarian biner, yang berjalan dalam kasus terburuk
- Namun, menambahkan elemen baru ke array yang diurutkan bisa jadi mahal. elemen harus disisipkan di tempat yang tepat
Kelas Java Array berisi implementasi pencarian biner, Python menawarkan algoritma membagi dua yang serupa, dan Go juga memiliki beberapa metode pencarian biner
Daftar tertaut
Jika Anda perlu menambahkan atau menghapus elemen berulang kali di awal atau akhir daftar, Anda mungkin ingin mempertimbangkan daftar tertaut
- Dalam daftar tertaut tunggal Anda dapat menambahkan elemen di kedua ujungnya dalam waktu konstan, dan juga menghapus elemen pertama dalam waktu konstan
- Dalam daftar tertaut ganda, Anda juga dapat menghapus elemen terakhir dalam waktu konstan
- Namun, pengindeksan sangat mahal. Untuk menemukan elemen pada indeks tertentu, Anda perlu melintasi daftar
Kelas Java LinkedList mengimplementasikan daftar tertaut ganda, Python menawarkan , dan Go juga memiliki paket daftar
Pohon pencarian biner
Pohon pencarian biner yang seimbang menyimpan item dalam urutan terurut dan menawarkan pencarian, penambahan, dan penghapusan item yang efisien
- Sebagian besar operasi dasar (mis. g. tambah, hapus, temukan dan min) jalankan
Di Java, pohon pencarian adalah bagian dari perpustakaan standar (TreeSet dan TreeMap), sedangkan Python dan Go tidak mendukungnya secara langsung.