Bu eğitimde, ana teoremin ne olduğunu ve yineleme ilişkilerini çözmek için nasıl kullanıldığını öğreneceksiniz.
Ana yöntem, formun tekrarlama ilişkilerini çözmek için bir formüldür:
T (n) = aT (n / b) + f (n), burada, n = girişin boyutu a = özyinelemedeki alt problemlerin sayısı n / b = her alt problemin boyutu. Tüm alt problemlerin aynı boyutta olduğu varsayılır. f (n) = problemi bölme maliyetini ve çözümleri birleştirmenin maliyetini içeren yinelemeli çağrının dışında yapılan işin maliyeti Burada, a ≧ 1 ve b> 1 sabitler ve f (n) asimptotik olarak pozitiftir işlevi.
Asimptotik olarak pozitif bir fonksiyon, yeterince büyük bir n değeri için sahip olduğumuz anlamına gelir f(n)> 0.
Ana teorem, yineleme ilişkilerinin (böl ve yönet algoritmaları) zaman karmaşıklığının basit ve hızlı bir şekilde hesaplanmasında kullanılır.
Ana Teorem
Eğer a ≧ 1ve b> 1sabitler ve f(n)asimptotik pozitif fonksiyonu ile verilmektedir yinelemeli ilişkinin daha sonra zaman karmaşıklığıdır
T (n) = aT (n / b) + f (n) burada, T (n) aşağıdaki asimptotik sınırlara sahiptir: 1. Eğer f (n) = O (n log b a-ϵ ) ise T (n ) = Θ (n log b a ). 2. Eğer f (n) = Θ (n log b a ) ise, T (n) = Θ (n log b a * log n). 3. Eğer f (n) = Ω (n log b a + ϵ ) ise T (n) = Θ (f (n)). ϵ> 0 bir sabittir.
Yukarıdaki koşulların her biri şu şekilde yorumlanabilir:
- Her seviyedeki alt problemleri çözmenin maliyeti belirli bir faktör kadar artarsa, değeri
f(n)polinomik olarak daha küçük olacaktır . Böylece, zaman karmaşıklığı, son seviyenin maliyeti, yani.nlogb anlogb a - Her seviyede alt problemi çözmenin maliyeti hemen hemen eşitse, o zaman değeri
f(n)olacaktır . Böylece, zaman karmaşıklığı toplam düzey sayısının katı olacaktır , yani.nlogb af(n)nlogb a * log n - Her seviyedeki alt problemleri çözmenin maliyeti belirli bir faktör kadar azalırsa, değeri
f(n)polinomik olarak daha büyük olacaktır . Böylece, zaman karmaşıklığı maliyeti ile baskı altına alınır .nlogb af(n)
Çözülmüş Ana Teorem Örneği
T (n) = 3T (n / 2) + n2 Burada, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1.58 <2 yani. f (n) <n log b a + ϵ , burada, ϵ bir sabittir. Durum 3 burada ima eder. Böylece, T (n) = f (n) = Θ (n 2 )
Ana Teorem Sınırlamaları
Ana teorem şu durumlarda kullanılamaz:
- T (n) monoton değildir. Örneğin.
T(n) = sin n f(n)bir polinom değildir. Örneğin.f(n) = 2n- a sabit değildir. Örneğin.
a = 2n a < 1
