Analisis Algoritma : UKURAN EFISIENSI ALGORITMA

Soal

1.Mengapa kita memerlukan algoritma yang efisien.

2.Bagaimana langkah untuk menentukan ukuran efisiensi waktu:

• a)    Bagaiamana menentukan problem size (n).
• b)      Bagaiamana menentukan operasi dominan
• c)      Bagaiamana menentukan fungsi langkah
• d)     Bagaiamana menentukan kompleksitas waktu O(f(n))

3.Apa Efisiensi Memory.space dan berikan contohnya.

4.Apa yang dimaksud dengan kemudahan impelemntasi suatu algoritma.

5.Bagaimana menentukan Stabilitas suatu algoritma.

Jawab :

11. Karena kita mermelukan efesien waktu dan memori,meskipun algoritma memberikan keluaran yang benar (yang mendekatai) , tetapi jika harus menunggu berjam jam untuk mendapatkan keluarannya , algoritma tersebut biasanya tidak akan dipakai, karena setiap orang menginginkan keluaran yang cepat, Begitu juga dengan memori.

Dan waktu tempuh suatu program sangat bergantung pada :

·         Banyak data ke problem size.

·         Spesifikasi computer ke Hardware (RAM,PROSESOR,dll).

·         Compiler ke software.

·         Tegangan listrik.

·         Dll ke programer

22. efisiensi waktu algoritma diukur dalam satuan n (problem size). terdapat 4 langkah untuk menentukan ukuran efisiensi waktu, antara lain:

• Menentukan problem size (n)
• Menentukan operasi dominan
• Menentukan Fungsi langkah → g(n)
• Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

a. menentukan problem size (n).  
 

        b. menentukan operasi dominan.

operasi dominan merupakan operasi yang paling banyak dilakukan, sesuai konteks permasalahan. misalkan pada algoritma menentukan nilai max/ min, operasi dominannya adalah operasi perbandingan ">" atau "<". pada algoritma searching operasi dominannya adalah operasi "=".

b.  C. Menentukan Fungsi langkah → g(n)

-          g (n) = banyak kali operasi dominan dilakukan (dalam n )

 

Pada contoh algoritma ini di perboleh keadaan  best case, yakni ketika data terurut ascending ; dan sebaliknya akan di perbolehkan keadaan worst case , yakni ketika data terurut descending atau data terbesar berada di X(1)

ad. Menentukan kompleksitas waktu O(f(n)) (Big Oh function)

Suatu algoritma dengan fungsi langkah g(n) di katakana mempunyai konpleksitas waktu O(f(n)) jika terdapat konstanta c > 0 sedemikian hingga : g(n) ≤ c.f(n) untuk n > n₀

Ø  Algoritma MaxMin,CountingSort            - g(n) = 2n – 2             - O(n) linier

Ø  Algoritma Bubblesort                               - g(n) = n²/2 – n/ 2       - O(n²) kwadratik

Ø  Algoritma perkalian 2 Matrix _{n x n}                  - g(n) = n³ + kn            - O(n³) kubik

Ø  Algoritma MergeSort ,QuickSort                         - g(n) = (n log n)          - O(nlogn) logaritmik

23. Efesiensi Memory/space adalah menentukan besar memory yang di perlukan oleh suatu algoritma.

Kebutuhan memory (space ) suatu algoritma jiga tidak bias di ukur dalam satuan memory (byte,KB) ,karena kebutuhan memory yang sebenarnya bergantung dari banyak data dan struktur datanya . kebutuhan memory dari suatu algoritma di ukur dalam satuan problem size n.

Contoh : penulihsan sebuah algoritma di dalam sebuah program.

  4. kemudahan impelemntasi suatu algoritma adalah mengukur seberapa mudah / sederhana algoritma tersebut di buat programnya , hal ini biasa di lihat dari teknik perancangannya atau struktur data yang di gunakan .

  5. stabilitas suatu algoritma dapat di lihat dari kesetabilan index data untuk data yang sama

contoh :