Notasi Asymptot

Daftar Isi
  1. Notasi Asimptotik: Urutan Pertumbuhan
  2. Urutan Pertumbuhan
  3. Notasi Ω (Omega), Θ (Theta), dan O (Big O)
  4. Nama-Nama dari Fungsi Pembatas
  5. Notasi O (Big O)
  6. Notasi Θ (Big Theta)
  7. Contoh-Contoh
  8. Sifat-Sifat
  9. Apa Yang Diimplikasikan oleh Properti Asimptotik bagi Sebuah Algoritma?
  10. Kelas Efisiensi Asimptotik Dasar
  11. Efisiensi Waktu Algoritma Non-Rekursif
  12. Contoh 1: Elemen Maksimum
  13. Contoh 2: Masalah Unik Elemen
  14. Contoh 3: Perkalian Matriks
  15. Contoh 4: Menghitung Digit Biner
  16. Download Materi Power Point
  17. Referensi


Notasi Asimptotik: Urutan Pertumbuhan

Latar Belakang

Misalkan, dalam kasus terburuk, suatu masalah dapat diselesaikan dengan menggunakan dua algoritma yang berbeda, dengan kompleksitas waktu:

 

Yang mana yang lebih baik?

Solusi: Abaikan konstanta dan suku dengan orde yang rendah

Kita menggunakan Notasi Asimptotik (Ω, Θ, dan O)


Urutan Pertumbuhan

Nilai (beberapa yang bersifat perkiraan) dari beberapa fungsi penting untuk analisis algoritma.


Notasi Ω (Omega), Θ (Theta), dan O (Big O)


Nama-Nama dari Fungsi Pembatas

  • f(n) = O(g(n)) berarti C x g(n) adalah batas atas dari f(n);

 

  • f(n) = Ω(g(n)) berarti C x g(n) adalah batas bawah dari f(n);

 

  • f(n) = Θ(g(n)) berarti C1 x g(n) adalah batas atas dari f(n) dan C2 x g(n) adalah batas bawah dari f(n).

Notasi O (Big O)

f(n) = Ω(g(n)): g(n) adalah batas bawah secara asimptotik untuk f(n). Artinya, f tidak tumbuh lebih cepat daripada g.


Notasi Θ (Big Theta)

f(n) = Θ(g(n)): g(n) adalah batas yang ketat secara asimptotik untuk f(n). Artinya, g(n) adalah batas yang pas untuk f(n).

 

Contoh-contoh dari Θ (Big Theta)

False, karena C1 dan C2 harus lebih besar dari 0.


Contoh-Contoh

Pikirkan kesetaraan sebagai arti dalam himpunan fungsi.


Sifat-Sifat

Transitivitas:

  • Jika f = O(h) dan g = O(h), maka f = O(h).
  • Jika f = Ω(g) dan g = Ω(h), maka f = Ω(h).
  • Jika f = Θ(g) dan g = Θ(h), maka f = Θ(h).

Aditivitas:

  • Jika f = O(h) dan g = O(h), maka f + g = O(h).
  • Jika f = Ω(h) dan g = Ω(h), maka f + g = Ω(h).
  • Jika f = Θ(h) dan g = O(h), maka f + g = Θ(h).

 

Tugas: Berdasarkan definisi Ω, Θ, dan O, buktikan bahwa:


Apa Yang Diimplikasikan oleh Properti Asimptotik bagi Sebuah Algoritma?

Bagaimana efisiensi keseluruhan dari algoritma ini?


Kelas Efisiensi Asimptotik Dasar


Efisiensi Waktu Algoritma Non-Rekursif

Rencana Umum untuk Analisis

  • Tentukan parameter n yang mengindikasikan ukuran input
  • Identifikasi operasi dasar algoritma
  • Tentukan kasus terburuk, rata-rata, dan terbaik untuk input ukuran n
  • Atur jumlah kali operasi dasar dijalankan
  • Sederhanakan jumlah tersebut menggunakan rumus dan aturan standar

Contoh 1: Elemen Maksimum

Menentukan nilai elemen terbesar dalam sebuah array yang diberikan

Input: Sebuah array A[0..n -1] dari angka real

Output: Nilai elemen terbesar dalam A


Contoh 2: Masalah Unik Elemen

Menentukan apakah semua elemen dalam sebuah array yang diberikan adalah unik atau tidak.

Input: Sebuah array A[0..n -1]

Output: Mengembalikan "true" jika semua elemen dalam A unik, dan "false" jika sebaliknya.


Contoh 3: Perkalian Matriks

Mengalikan dua matriks berukuran n-by-n menggunakan algoritma berdasarkan definisi.

Input: Dua matriks berukuran n-by-n, A dan B

Output: Matriks C = AB


Contoh 4: Menghitung Digit Biner

Input: Sebuah bilangan bulat desimal positif n

Output: Jumlah digit biner dalam representasi biner n, count <- 1

Hal ini tidak dapat diselidiki dengan cara yang sama seperti contoh-contoh sebelumnya.


Download Materi Power Point

https://drive.google.com/drive/folders/16HL651AUf3BihpbvMNgEfEXPwUHbcPz-?usp=drive_link


Referensi

-