Struktur Data - Analisis Asymptotic

Analisis asimtotik dari suatu algoritme mengacu pada penentuan batas / pembingkaian matematis dari kinerja run-time-nya. Dengan menggunakan analisis asimtotik, kita dapat menyimpulkan kasus terbaik, kasus rata-rata, dan skenario kasus terburuk dari suatu algoritme.

Analisis asimtotik terikat dengan input, yaitu jika tidak ada input ke algoritme, disimpulkan untuk bekerja dalam waktu yang konstan. Selain "masukan", semua faktor lainnya dianggap konstan.

Analisis asimtotik mengacu pada penghitungan waktu berjalan operasi apa pun dalam unit komputasi matematika. Misalnya, waktu berjalan dari satu operasi dihitung sebagai f (n) dan mungkin untuk operasi lain dihitung sebagai g (n ² ). Ini berarti waktu berjalan operasi pertama akan meningkat secara linier dengan peningkatann dan waktu berjalan operasi kedua akan meningkat secara eksponensial saat nmeningkat. Begitu pula waktu berjalan kedua operasi akan hampir sama jikan sangat kecil.

Biasanya, waktu yang dibutuhkan oleh algoritme termasuk dalam tiga jenis -

Best Case - Waktu minimum yang dibutuhkan untuk pelaksanaan program.
Average Case - Waktu rata-rata yang dibutuhkan untuk eksekusi program.
Worst Case - Waktu maksimum yang dibutuhkan untuk pelaksanaan program.

Notasi Asymptotic

Berikut ini adalah notasi asimtotik yang umum digunakan untuk menghitung kompleksitas waktu berjalan suatu algoritme.

Ο Notasi
Ω Notasi
θ Notasi

Notasi Big Oh, Ο

Notasi Ο (n) adalah cara formal untuk menyatakan batas atas waktu berjalan suatu algoritma. Ini mengukur kompleksitas waktu kasus terburuk atau jumlah waktu terlama yang mungkin diperlukan algoritme untuk menyelesaikannya.

Misalnya, untuk suatu fungsi f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

Notasi Omega, Ω

Notasi Ω (n) adalah cara formal untuk menyatakan batas bawah waktu berjalan suatu algoritma. Ini mengukur kompleksitas waktu kasus terbaik atau jumlah waktu terbaik yang mungkin diperlukan algoritme untuk menyelesaikannya.

Misalnya, untuk suatu fungsi f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

Notasi Theta, θ

Notasi θ (n) adalah cara formal untuk menyatakan batas bawah dan batas atas dari waktu berjalan suatu algoritma. Ini direpresentasikan sebagai berikut -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Notasi Asymptotic Umum

Berikut ini adalah daftar beberapa notasi asimtotik yang umum -

konstan	-	Ο (1)
logaritma	-	Ο (log n)
linier	-	Ο (n)
n log n	-	Ο (n log n)
kuadrat	-	Ο (n ² )
kubik	-	Ο (n ³ )
polinomial	-	n ^{Ο (1)}
eksponensial	-	2 ^{Ο (n)}