materi

Konsep Dasar Struktur Data, Tipe Data Abstrak, dan Analisis Asimtotik

Konsep Dasar Struktur Data, ADT, dan Analisis Kompleksitas Asimtotik

Modul perkuliahan perdana Struktur Data yang mengkaji representasi data dalam memori komputer, konsep Tipe Data Abstrak (Abstract Data Type / ADT), serta teknik matematis dalam mengukur efisiensi algoritma melalui analisis kompleksitas waktu dan ruang.

1. Definisi dan Klasifikasi Struktur Data

Struktur data adalah cara sistematis dalam mengorganisasikan, mengelola, dan menyimpan data di memori sehingga operasi penelusuran, modifikasi, dan komputasi dapat dieksekusi secara optimal.

  • Struktur Data Linear: Elemen data tersusun secara sekuensial hierarkis, di mana setiap elemen terhubung langsung dengan elemen sebelum dan sesudahnya (contoh: Array, Linked List, Stack, Queue).
  • Struktur Data Non-Linear: Elemen data tidak disusun dalam urutan beruntun tunggal, melainkan membentuk keterhubungan bertingkat atau graf interkoneksi (contoh: Tree, Graph, Trie).

2. Analisis Kompleksitas Asimtotik (Big-O Notation)

Efisiensi suatu algoritma diukur berdasarkan laju pertumbuhan kebutuhan waktu komputasi T(n)T(n) dan konsumsi memori S(n)S(n) terhadap kenaikan ukuran masukan nn.

  • Notasi Big-O (Batas Atas / Worst Case): Menjamin bahwa konsumsi komputasi algoritma tidak akan melampaui konstanta pengali tertentu c⋅g(n)c \cdot g(n) untuk setiap n≥n0n \ge n_0.
  • Tingkatan Kompleksitas Standar:
    1. O(1)O(1): Kompleksitas Konstan (akses elemen array berbasis indeks).
    2. O(log⁡n)O(\log n): Kompleksitas Logaritmik (Binary Search pada array terurut).
    3. O(n)O(n): Kompleksitas Linier (Linear Search, perulangan tunggal).
    4. O(nlog⁡n)O(n \log n): Kompleksitas Linieritmik (Merge Sort, Heap Sort).
    5. O(n2)O(n^2): Kompleksitas Kuadratik (Bubble Sort, Insertion Sort, Nested Loop).
    6. O(2n)O(2^n): Kompleksitas Eksponensial (rekursi naif Fibonacci).

3. Tipe Data Abstrak (Abstract Data Type / ADT)

ADT mendefinisikan himpunan nilai data beserta spesifikasi operasi fungsional yang dapat dilakukan terhadapnya tanpa mengekspos detail implementasi internal ke pengguna modul.

Back to Academics