Struktur Data & Algoritma - Gambaran Umum
Struktur Data adalah cara sistematis untuk mengatur data agar dapat digunakan secara efisien. Istilah berikut adalah istilah dasar dari struktur data.
Interface- Setiap struktur data memiliki antarmuka. Antarmuka merepresentasikan rangkaian operasi yang didukung oleh struktur data. Antarmuka hanya menyediakan daftar operasi yang didukung, jenis parameter yang dapat mereka terima, dan jenis pengembalian dari operasi ini.
Implementation- Implementasi memberikan representasi internal dari struktur data. Implementasi juga memberikan definisi dari algoritma yang digunakan dalam pengoperasian struktur data.
Karakteristik Struktur Data
Correctness - Implementasi struktur data harus mengimplementasikan antarmuka dengan benar.
Time Complexity - Running time atau waktu pelaksanaan operasi struktur data harus sekecil mungkin.
Space Complexity - Penggunaan memori dari operasi struktur data harus sesedikit mungkin.
Kebutuhan Struktur Data
Karena aplikasi menjadi semakin kompleks dan data menjadi kaya, ada tiga masalah umum yang dihadapi aplikasi saat ini.
Data Search- Pertimbangkan inventaris 1 juta (10 6 ) item toko. Jika aplikasi untuk mencari item, itu harus mencari item dalam 1 juta (10 6 ) item setiap kali memperlambat pencarian. Seiring bertambahnya data, penelusuran akan menjadi lebih lambat.
Processor speed - Kecepatan prosesor meskipun sangat tinggi, turun terbatas jika datanya bertambah hingga miliaran catatan.
Multiple requests - Karena ribuan pengguna dapat mencari data secara bersamaan di server web, bahkan server yang cepat pun gagal saat mencari data.
Untuk mengatasi masalah yang disebutkan di atas, struktur data datang untuk menyelamatkan. Data dapat diatur dalam struktur data sedemikian rupa sehingga semua item mungkin tidak perlu dicari, dan data yang diperlukan dapat dicari hampir secara instan.
Kasus Waktu Eksekusi
Ada tiga kasus yang biasanya digunakan untuk membandingkan waktu eksekusi berbagai struktur data secara relatif.
Worst Case- Ini adalah skenario di mana operasi struktur data tertentu membutuhkan waktu maksimum yang diperlukan. Jika waktu kasus terburuk suatu operasi adalah ƒ (n) maka operasi ini tidak akan memakan waktu lebih dari ƒ (n) waktu di mana ƒ (n) mewakili fungsi n.
Average Case- Ini adalah skenario yang menggambarkan waktu eksekusi rata-rata dari suatu operasi struktur data. Jika sebuah operasi membutuhkan ƒ (n) waktu dalam eksekusi, maka operasi m akan memakan waktu mƒ (n) waktu.
Best Case- Ini adalah skenario yang menggambarkan waktu eksekusi sesingkat mungkin dari suatu operasi struktur data. Jika sebuah operasi membutuhkan ƒ (n) waktu dalam eksekusi, maka operasi sebenarnya mungkin membutuhkan waktu sebagai bilangan acak yang akan menjadi maksimum sebagai ƒ (n).
Terminologi Dasar
Data - Data adalah nilai atau kumpulan nilai.
Data Item - Item data mengacu pada satu unit nilai.
Group Items - Item data yang dibagi menjadi sub item disebut sebagai Item Grup.
Elementary Items - Item data yang tidak dapat dibagi disebut sebagai Item Dasar.
Attribute and Entity - Entitas adalah yang berisi atribut atau properti tertentu, yang mungkin diberi nilai.
Entity Set - Entitas dengan atribut serupa membentuk kumpulan entitas.
Field - Bidang adalah satu unit dasar informasi yang mewakili atribut dari suatu entitas.
Record - Record adalah kumpulan nilai field dari suatu entitas.
File - File adalah kumpulan catatan entitas dalam kumpulan entitas tertentu.