Struktur Data dan Algoritme
Struktur Data & Algoritme (Data Structures & Algorithms)
Data structure (aka ADT – Abstract Data Type) = representation + operations operation allowed may vary between data structure • • • •
Wrap Up
Denny (
[email protected]) Suryana Setiawan (
[email protected]) Fakultas Ilmu Komputer Universitas Indonesia
insert delete access (find / get) update
Algoritme Suatu set instruksi yang harus diikuti oleh computer untuk memecahkan suatu masalah. Program harus berhenti dalam batas waktu yang wajar (reasonable) Tidak terikat pada programming language atau bahkan paradigma pemrograman (mis. Procedural vs Object-Oriented)
Semester Genap - 2004/2005
Version 2.0 - Internal Use Only
Struktur Data dan Algoritme
Objectives
SDA/WRAP-UP/V2.0/3
Mengulas kembali dan merangkum konsep-konsep penting dalam kuliah Struktur Data dan Algoritme
Mengapa dalam penyimpanan data diperlukan sebuah struktur? Supaya lebih mudah/efisien dalam pengaksesan/pemrosesan data tersebut Mengapa struktur data penting? Bukankan hanya algoritme saja yang menentukan running time? Problem: mencari sebuah integer dalam data-data yang terurut Algoritme: binary search!!! Struktur data: • binary search pada array? • binary search pada linked list? doubly linked list?
SDA/WRAP-UP/V2.0/2
Struktur data mana yang lebih efisien? SDA/WRAP-UP/V2.0/4
1
Struktur Data dan Algoritme
Contoh Lain: Problem: mengevaluasi ekspresi: (5 + 2) * 7 menggunakan struktur data Stack
struktur data + algoritme = program Algorithms require the use of a proper representation of data to achieve efficiency
Struktur data membantu tercapainya Component Reusability. Menerapkan konsep OO paradigm: encapsulation, information-hiding dan abstraction.
Analisa Algoritme: how?
Notasi O (sering disebut sebagai “notasi big-Oh”) Digunakan sebagai bahasa untuk membahas efisiensi dari sebuah algoritme: log n, linier, n log n, n2, n3, ... Big Oh digunakan untuk merepresentasikan laju pertumbuhan (growth rate) Dominant Term Mengapa hanya suku yang memiliki pangkat tertinggi/dominan saja yang diperhatikan? Untuk n yang besar, suku dominan lebih mengindikasikan perilaku dari algoritme. Untuk n yang kecil, suku dominan tidak selalu mengindikasikan perilakunya, tetapi program dengan input kecil umumnya berjalan sangat cepat sehingga kita tidak perlu perhatikan.
SDA/WRAP-UP/V2.0/5
Analisa Algoritme: what?
Orde Fungsi Running-Time
Mengukur jumlah sumber daya (time dan space) yang diperlukan oleh sebuah algoritme
Waktu yang diperlukan (running time) oleh sebuah algoritme cenderung tergantung pada jumlah input yang diproses.
Î Running time dari sebuah algoritme adalah fungsi dari jumlah inputnya
SDA/WRAP-UP/V2.0/7
Selalu tidak terikat pada platform (mesin + OS), bahasa pemrograman, kualitas kompilator atau bahkan paradigma pemrograman (mis. Procedural vs Object-Oriented)
SDA/WRAP-UP/V2.0/6
Function c log N log2 N N N log N N2 N3 2N N!
Name Constant Logarithmic Log-squared Linear N log N Quadratic Cubic Exponential Factorial SDA/WRAP-UP/V2.0/8
2
Fungsi Running-Time
Sorting
Untuk input yang sedikit, beberapa fungsi lebih cepat dibandingkan dengan yang lain.
Sorting = pengurutan Sorted = terurut menurut kaidah tertentu Sorting umumnya dipakai dalam pre-processing untuk mempercepat proses-proses berikutnya. misalnya: • mencari elemen Î binary search • menghilangkan duplikasi
SDA/WRAP-UP/V2.0/9
Fungsi Running-Time (2)
SDA/WRAP-UP/V2.0/11
Bubble Sort
Untuk input yang besar, beberapa fungsi runningtime sangat lambat - tidak berguna.
SDA/WRAP-UP/V2.0/10
Idea: Gelembung udara (ringan) dalam air akan naik ke atas, air (berat) yang di atasnya akan turun. Worst case: O(n2) Best case: O(n) -- when? why?
SDA/WRAP-UP/V2.0/12
3
Selection sort & Insertion sort
Incremental approach 2 array: terurut dan tidak terurut Awalnya array yang terurut kosong. Kosong Æ sorted Ambil 1 elemen dari array yang tidak terurut, masukkan ke array yang terurut sedemikian rupa sehingga tetap menjaga keterurutan data (invariant). Lakukan sebanyak n kali. Selection: Ambil 1 element yang terkecil dari array yang tidak terurut Î O(n) letakkan di paling belakang di array yang terurut Î O(1) Insertion: Ambil 1 element (yang mana saja) dari array yang tidak terurut Î O(1) sisipkan di posisi yang benar dalam array yang terurut supaya array tetap terurut Î O(n)
Other Sorting Algorithms
Shell Sort Heap Sort Menggunakan struktur data heap Heapify Î O(n) Percolate Down O(log n) dilakukan n kali Total: O(n log n) Bucket Sort / Postman Sort Tukang Pos mengurutkan surat berdasarkan kode pos (5 digit). Running time: O(nk) • k = jumlah digit
External Sorting Algorithms Jumlah data >>> jumlah memory yang tersedia
SDA/WRAP-UP/V2.0/13
Merge Sort & Quick sort
Divide and Conquer approach Î Recursive Merge sort: Divide: bagi array menjadi 2 bagian yang sama besar Î O(1) Conquer: • kalau panjang array 0 atau 1 Æ sudah terurut • menggabungkan (merge) dua array yang sudah terurut Î O(n)
Dilakukan log n kali (best case dan worst case) Quick sort: Divide: bagi array menjadi 2 bagian Î O(n)
• bagian 1 berisi elemen < pivot • bagian 2 berisi elemen >= pivot
Conquer:
Dilakukan log n kali (best case), n kali (worst case) Î tergantung cara pemilihan pivot. SDA/WRAP-UP/V2.0/14
SDA/WRAP-UP/V2.0/15
Struktur Data
Linked List vs. Array representation/storage: • contiguous vs. non-contiguous • growable (dynamic size) vs. static • overhead?
Access? Stack vs. Queue Access? Implementation of Stack and Queue
• Linked List vs. Array
• menyambungkan bagian 1 dan bagian 2 Î O(1)
SDA/WRAP-UP/V2.0/16
4
Struktur Data
Graph
Tree Binary Tree
• Representation? • Traversing: • DFS: Pre-Order, In-Order, Post-Order • BFS: Level-Order
Binary Search Tree (BST) Balanced BST • AVL Tree: Height as balancing information • Red-Black Tree: Colour as balancing information
n-ary Tree Balanced n-ary Tree • Complete Tree: but node can have x children or y children • 2-3 Tree, a-b Tree • External Data Structure: B Tree, B+Tree
Terminology vertices/nodes (simpul) edges (sisi/busur) adjacent vertices undirected vs. directed graph degree (of a vertex), for directed graph: in-degree, outdegree unweighted vs. weighted graph path, simple path, cycle DAG (Directed Acyclic Graph) connected graph subgraph
Trie SDA/WRAP-UP/V2.0/17
Struktur Data
Graph
Hash Table Hash Function: map key to address Collition resolution:
• Closed Hashing (aka Open addressing) • Linear Probing Æ primary clustering • Quadratic Probing Æ secondary clustering • Double Hashing • Open Hasing (aka Separate Chaining)
SDA/WRAP-UP/V2.0/19
Priority Queue Implemented using Heap • Insert: Percolate Up – O(log n) • Delete: Percolate Down – O(log n) • Heapify SDA/WRAP-UP/V2.0/18
Representation Edge List Adjancency List Adjancency Matrix Which representation is the best? Graph Problem: Topological Sorting Shortest Path: Djikstra Minimum Spanning Tree: Prim, Kruskal
SDA/WRAP-UP/V2.0/20
5
Selamat Ujian!
SDA/WRAP-UP/V2.0/21
6