DataStructure And Algo
1.0.0
Struktur data adalah cara khusus untuk mengatur dan menyimpan data di komputer sedemikian rupa sehingga kami dapat melakukan operasi pada data yang disimpan secara lebih efisien. Struktur data memiliki ruang lingkup penggunaan yang luas dan beragam di seluruh bidang ilmu komputer dan rekayasa perangkat lunak. Struktur data sedang digunakan di hampir setiap program atau sistem perangkat lunak yang telah dikembangkan. Selain itu, struktur data berada di bawah dasar -dasar ilmu komputer dan rekayasa perangkat lunak. Ini adalah topik utama dalam pertanyaan wawancara rekayasa perangkat lunak. Oleh karena itu sebagai pengembang, kita harus memiliki pengetahuan yang baik tentang struktur data.
Array adalah struktur dengan ukuran tetap, yang dapat menampung item dari tipe data yang sama. Ini bisa berupa array bilangan bulat, serangkaian bilangan titik mengambang, serangkaian string atau bahkan array array (seperti array 2 dimensi). Array diindeks, artinya akses acak dimungkinkan.
Memasukkan elemen ke elemen array dan penghapusan dari array tidak dapat dilakukan langsung karena array tetap dalam ukuran. Jika Anda ingin memasukkan elemen ke array, pertama -tama Anda harus membuat array baru dengan ukuran yang meningkat (ukuran saat ini + 1), salin elemen yang ada dan tambahkan elemen baru. Hal yang sama berlaku untuk penghapusan dengan array baru dengan ukuran berkurang.
Daftar tertaut adalah struktur berurutan yang terdiri dari urutan item dalam urutan linier yang saling terkait. Oleh karena itu, Anda harus mengakses data secara berurutan dan akses acak tidak dimungkinkan. Daftar Tertaut memberikan representasi set dinamis yang sederhana dan fleksibel.
Tumpukan adalah LIFO (terakhir di First Out - elemen yang ditempatkan pada akhirnya dapat diakses pada awalnya) struktur yang umumnya dapat ditemukan dalam banyak bahasa pemrograman. Struktur ini dinamai "tumpukan" karena menyerupai tumpukan dunia nyata-setumpuk piring.
Digunakan untuk evaluasi ekspresi (misalnya: algoritma shunting-yard untuk parsing dan mengevaluasi ekspresi matematika). Digunakan untuk menerapkan panggilan fungsi dalam pemrograman rekursi.
Antrian adalah FIFO (pertama di First Out - elemen yang ditempatkan pada awalnya dapat diakses pada awalnya) struktur yang umumnya dapat ditemukan dalam banyak bahasa pemrograman. Struktur ini dinamai "antrian" karena menyerupai antrian dunia nyata-orang-orang yang menunggu dalam antrian.
Digunakan untuk mengelola utas dalam multithreading. Digunakan untuk mengimplementasikan sistem antrian (misalnya: antrian prioritas).
Tabel hash adalah struktur data yang menyimpan nilai yang memiliki kunci yang terkait dengan masing -masing. Selain itu, ini mendukung pencarian secara efisien jika kita tahu kunci yang terkait dengan nilainya. Oleh karena itu sangat efisien dalam memasukkan dan mencari, terlepas dari ukuran data.
Pengalamatan langsung menggunakan pemetaan satu-ke-satu antara nilai dan kunci saat disimpan dalam tabel. Namun, ada masalah dengan pendekatan ini ketika ada sejumlah besar pasangan nilai kunci. Tabel akan sangat besar dengan begitu banyak catatan dan mungkin tidak praktis atau bahkan tidak mungkin disimpan, mengingat memori yang tersedia di komputer khas. Untuk menghindari masalah ini, kami menggunakan tabel hash .
Fungsi khusus bernama fungsi hash (h) digunakan untuk mengatasi masalah yang disebutkan di atas dalam pengalamatan langsung. Dalam mengakses langsung, nilai dengan kunci K disimpan dalam slot k. Menggunakan fungsi hash, kami menghitung indeks tabel (slot) yang setiap nilainya. Nilai yang dihitung menggunakan fungsi hash untuk kunci yang diberikan disebut nilai hash yang menunjukkan indeks tabel tempat nilai dipetakan.
Pohon adalah struktur hierarkis di mana data diatur secara hierarkis dan dihubungkan bersama. Struktur ini berbeda dari daftar tertaut sedangkan, dalam daftar tertaut, item ditautkan dalam urutan linier. Berbagai jenis pohon telah dikembangkan selama beberapa dekade terakhir, agar sesuai dengan aplikasi tertentu dan memenuhi kendala tertentu. Beberapa contoh adalah pohon pencarian biner, pohon B, trap, pohon merah-hitam, pohon splay, pohon AVL dan pohon N-ary.
Pohon pencarian biner (BST), seperti namanya, adalah pohon biner di mana data diatur dalam struktur hierarkis. Struktur data ini menyimpan nilai dalam urutan yang diurutkan. Setiap node dalam pohon pencarian biner terdiri dari atribut berikut.
Pohon pencarian biner menunjukkan properti unik yang membedakannya dari pohon lain. Properti ini dikenal sebagai properti ** biner-pencarian-pohon **.
Tumpukan adalah kasus khusus dari pohon biner di mana node induk dibandingkan dengan anak -anak mereka dengan nilai -nilai mereka dan disusun.
Tumpukan bisa dari 2 jenis.
Grafik terdiri dari satu set simpul atau node yang terbatas dan satu set tepi yang menghubungkan simpul -simpul ini.
Urutan grafik adalah jumlah simpul dalam grafik. Ukuran grafik adalah jumlah tepi dalam grafik.
Dua node dikatakan berdekatan jika mereka terhubung satu sama lain dengan tepi yang sama.
Grafik G dikatakan sebagai grafik diarahkan jika semua ujungnya memiliki arah yang menunjukkan apa verteks awal dan apa verteks akhir . Kami mengatakan bahwa (u, v) adalah insiden dari atau meninggalkan vertex u dan merupakan insiden untuk atau memasuki vertex v. Loop-mandiri: tepi dari vertex ke dirinya sendiri.
Grafik G dikatakan sebagai grafik yang tidak diarahkan jika semua ujungnya tidak memiliki arah. Ini bisa masuk kedua cara antara kedua simpul.
Jika titik tidak terhubung ke simpul lain dalam grafik, dikatakan diisolasi .
Sebuah trie adalah struktur data pengambilan informasi seperti pohon yang nodenya menyimpan huruf-huruf alfabet. Ini juga dikenal sebagai pohon digital atau pohon radix atau pohon awalan.
Trie adalah struktur data pengambilan informasi yang efisien. Menggunakan trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci di pohon pencarian biner, BST yang seimbang akan membutuhkan waktu sebanding dengan m * log n, di mana m adalah panjang string maksimum dan n adalah jumlah kunci di pohon. Menggunakan trie, kita dapat mencari kunci dalam waktu O (m) .
1. TRIE STANDAR : Ini adalah pohon yang dipesan seperti struktur data.
2. TRIE Terkompresi : Digunakan untuk mencapai optimasi ruang. TRIE terkompresi adalah versi canggih dari trie standar.
3. Suffix Trie : A Suffix Trie adalah versi canggih dari trie terkompresi.
Dengan trie, kita dapat memasukkan dan menemukan string dalam waktu O (l) di mana L mewakili panjang satu kata. Ini jelas lebih cepat dari BST. Ini juga lebih cepat dari hashing karena cara diterapkan. Kami tidak perlu menghitung fungsi hash apa pun. Keuntungan lain dari trie adalah, kita dapat dengan mudah mencetak semua kata dalam urutan abjad yang tidak mudah dimungkinkan dengan hashing.
Pemrograman dinamis adalah teknik yang memecah masalah menjadi sub-masalah , dan menyimpan hasilnya untuk tujuan di masa depan sehingga kita tidak perlu menghitung hasilnya lagi. Subproblem dioptimalkan untuk mengoptimalkan solusi keseluruhan dikenal sebagai properti substruktur optimal. Penggunaan utama pemrograman dinamis adalah untuk memecahkan masalah optimasi. Di sini, masalah optimasi berarti bahwa ketika kita mencoba mengetahui solusi minimum atau maksimum suatu masalah. Pemrograman dinamis menjamin untuk menemukan solusi optimal dari suatu masalah jika solusi ada.
Algoritma kompleksitas waktu o (1) Mencari elemen tertentu dalam array, seperti ini misalnya: cetak (my_array [97]) tidak peduli ukuran array, elemen dapat dilihat secara langsung, itu hanya membutuhkan satu operasi. (Ngomong -ngomong, ini bukan algoritma, tetapi dapat membantu kita memahami bagaimana kompleksitas waktu bekerja.)
O (n) Menemukan nilai terendah. Algoritma harus melakukan operasi N dalam array dengan nilai n untuk menemukan nilai terendah, karena algoritma harus membandingkan setiap nilai satu kali.
O (n 2) Sortir gelembung, Sortir Seleksi dan Sortir Penyisipan adalah algoritma dengan kompleksitas waktu ini. Alasan kompleksitas waktu mereka dijelaskan di halaman untuk algoritma ini.
Set data besar memperlambat algoritma ini secara signifikan. Dengan hanya peningkatan N dari 100 menjadi 200 nilai, jumlah operasi dapat meningkat sebanyak 30000!
O (n log n) algoritma quicksort rata -rata lebih cepat daripada tiga algoritma penyortiran yang disebutkan di atas, dengan O (n log n) menjadi rata -rata dan bukan waktu kasus terburuk. Waktu kasus terburuk untuk quicksort juga o (n 2), tetapi itu adalah waktu rata -rata yang membuat quicksort sangat menarik. Kami akan belajar tentang Quicksort nanti.
Referensi diambil dari tautan ini - Sourav Saini?
