Pada Artikel kali ini kita akan Mengenal Tentang Apa itu Analisis Asimtotik dalam Algoritma ? . Analisis asimtotik (Symtotic Analysis) dalam algoritma, mengacu mendefinisikan matematika boundation / framing pada kinerja run-time.
Pada Artikel kali ini kita akan Mengenal Tentang Apa itu Analisis Asimtotik dalam Algoritma ? . Analisis asimtotik (Symtotic Analysis) dalam algoritma, mengacu mendefinisikan matematika boundation / framing pada kinerja run-time. Menggunakan analisis asimtotik, kita bisa sangat baik menyimpulkan kasus terbaik, kasus rata-rata dan skenario kasus terburuk dari algoritma.
Analisis Asimtotik dalam Algoritma yang masukan terikat yaitu, jika tidak ada masukan untuk algoritma disimpulkan untuk bekerja dalam waktu yang konstan. Selain "masukan" semua faktor lain dianggap konstan.
Analisis Asimtotik dalam Algoritma mengacu menghitung waktu berjalan dari setiap operasi di unit matematika komputasi. Misalnya, waktu berjalan dari satu operasi dihitung sebagai f(n) dan mungkin untuk operasi yang lain itu dihitung sebagai g(n2). Yang berarti operasi pertama berjalan waktu akan meningkat secara linear dengan peningkatan n dan berjalan saat operasi kedua akan meningkat secara eksponensial ketika n meningkat. Demikian pula saat berjalan dari kedua operasi akan hampir sama jika n secara signifikan kecil.
Biasanya, waktu yang dibutuhkan oleh sebuah algoritma jatuh di bawah tiga jenis -
- Kasus terbaik - waktu minimum yang diperlukan untuk pelaksanaan program.
- Kasus Rata-rata - rata waktu yang dibutuhkan untuk pelaksanaan program.
- Kasus terburuk - Waktu maksimum yang diperlukan untuk pelaksanaan program.
Notasi Asimtotik dalam Algoritma
Berikut ini adalah umum digunakan notasi asimtotik digunakan dalam menghitung menjalankan kompleksitas waktu dari algoritma.
- Notasi Ο
- Notasi Ω
- Notasi θ
Notasi Asimtotik O
The Ο(n) adalah cara formal untuk mengekspresikan batas atas waktu algoritma ini berjalan. Ini mengukur kompleksitas waktu atau jumlah terpanjang waktu algoritma mungkin dapat dilakukan untuk menyelesaikan.
Misalnya, untuk fungsi f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
Omega Notation, Ω
The Ω(n) adalah cara formal untuk mengekspresikan batas bawah waktu algoritma ini berjalan. Mengukur terbaik kompleksitas waktu kasus atau jumlah terbaik dari waktu algoritma mungkin dapat dilakukan untuk menyelesaikan.
Misalnya, untuk fungsi f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
Theta Notation, θ
The θ(n) adalah cara formal untuk mengekspresikan batas bawah dan batas atas waktu algoritma ini berjalan. Hal ini direpresentasikan sebagai berikut -
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
Notasi umum Asimtotik
| constant | − | Ο(1) |
| logarithmic | − | Ο(log n) |
| linear | − | Ο(n) |
| n log n | − | Ο(n log n) |
| quadratic | − | Ο(n2) |
| cubic | − | Ο(n3) |
| polynomial | − | nΟ(1) |
| exponential | − | 2Ο(n) |
COMMENTS