Veri Yapıları - Asimptotik Analiz

Bir algoritmanın asimptotik analizi, çalışma zamanı performansının matematiksel sınırını / çerçevelemesini tanımlamayı ifade eder. Asimptotik analizi kullanarak, bir algoritmanın en iyi durumunu, ortalama durumunu ve en kötü senaryosunu çok iyi bir şekilde sonuçlandırabiliriz.

Asimptotik analiz girdiye bağlıdır, yani algoritmaya herhangi bir girdi yoksa, sabit bir zamanda çalıştığı sonucuna varılır. "Girdi" dışında diğer tüm faktörler sabit kabul edilir.

Asimptotik analiz, herhangi bir işlemin çalışma süresini matematiksel hesaplama birimleriyle hesaplamayı ifade eder. Örneğin, bir işlemin çalışma süresi f (n) olarak hesaplanır ve başka bir işlem için g (n ² ) olarak hesaplanabilir . Bu, ilk işlem çalışma süresinin, artışla doğrusal olarak artacağı anlamına gelir.n ve ikinci işlemin çalışma süresi katlanarak artacaktır. nartışlar. Benzer şekilde, her iki işlemin çalışma süresi de hemen hemen aynı olacaktır.n önemli ölçüde küçüktür.

Genellikle, bir algoritmanın gerektirdiği süre üç türe ayrılır -

Best Case - Programın yürütülmesi için gereken minimum süre.
Average Case - Programın yürütülmesi için gereken ortalama süre.
Worst Case - Programın yürütülmesi için gereken maksimum süre.

Asimptotik Gösterimler

Bir algoritmanın çalışma süresi karmaşıklığını hesaplamak için yaygın olarak kullanılan asimtotik gösterimler aşağıdadır.

Ο Gösterim
Ω Gösterim
θ Gösterim

Büyük Oh Notasyonu, Ο

Ο (n) notasyonu, bir algoritmanın çalışma süresinin üst sınırını ifade etmenin resmi yoludur. En kötü durum zaman karmaşıklığını veya bir algoritmanın tamamlaması için alabileceği en uzun süreyi ölçer.

Örneğin, bir işlev için f(n)

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

Omega Notasyonu, Ω

Ω (n) notasyonu, bir algoritmanın çalışma süresinin alt sınırını ifade etmenin resmi yoludur. En iyi durum süresi karmaşıklığını veya bir algoritmanın tamamlaması için alabileceği en iyi süreyi ölçer.

Örneğin, bir işlev için f(n)

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

Theta Notasyonu, θ

Θ (n) notasyonu, bir algoritmanın çalışma süresinin hem alt sınırını hem de üst sınırını ifade etmenin resmi yoludur. Aşağıdaki gibi temsil edilir -

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

Yaygın Asimptotik Gösterimler

Aşağıda bazı yaygın asimptotik gösterimlerin bir listesi verilmiştir -

sabit	-	Ο (1)
logaritmik	-	Ο (günlük n)
doğrusal	-	Ο (n)
n log n	-	Ο (n log n)
ikinci dereceden	-	Ο (n ² )
kübik	-	Ο (n ³ )
polinom	-	n ^{Ο (1)}
üstel	-	2 ^{Ο (n)}