Python - Jenis Algoritma

Efisiensi dan akurasi algoritma harus dianalisis untuk membandingkannya dan memilih algoritma tertentu untuk skenario tertentu. Proses pembuatan analisis ini disebut analisis Asymptotic. Ini mengacu pada penghitungan waktu berjalan dari setiap operasi dalam unit komputasi matematika. Misalnya, waktu berjalan dari satu operasi dihitung sebagai f (n) dan mungkin untuk operasi lain dihitung sebagai g (n2). Ini berarti waktu operasi operasi pertama akan meningkat secara linier dengan kenaikan n dan waktu operasi operasi kedua akan meningkat secara eksponensial ketika n bertambah. Demikian pula, waktu berjalan kedua operasi akan hampir sama jika n sangat kecil.

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

Kasus Terbaik - Waktu minimum yang dibutuhkan untuk eksekusi program.
Average Case - Rata-rata waktu yang dibutuhkan untuk eksekusi program.
Kasus Terburuk - Waktu maksimum yang dibutuhkan untuk eksekusi 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)}