Master Teorem

1 / 25

ALGORİTMA ANALİZİCumhuriyet Üniversitesi Bilgisayar Mühendisliği Bölümü

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master Teorem I

Bir algoritmanın analizi yapılırken, ifadeyi yalnızca asimptotik notasyon ile belirttiğimizi hatırlayalım.

Rekursif algoritmalar için de bu durum farklı değildir.

Rekurans analizi yapılırken, hesaplamada kullanılan yöntemlerden biri de "Master Teorem" dir.

2 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master Teorem II

Teorem (Master Teorem)

T (n) aşağıdaki ifadeyi sağlayan monotonik artış gösteren bir fonksiyondur.

T (n) = aT (nb ) + f(n)

T (1) = c

Burada a ≥ 1, b ≥ 2, c > 0. If f (n) ∈ Θ(nd) ve d ≥ 0, buna göre

T (n) =

Θ(nd if) a < bd

Θ(nd log n if) a = bd

Θ(nlogb a if) a > bd

3 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremKoşullar

Şu durumlar için Master Teorem kullanılamaz

T (n) monoton değilse, ör: T (n) = sin n

f(n) polinomyal değilse, ör:(n) = 2T ( n2 ) + 2n

Örneklerde verilen durumlarda Master Teorem rekurans ilişkisini çözemez.

4 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a =

1

b =

2

d =

2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 1 < 22, case 1 applies.

Thus we conclude that

T (n) ∈ Θ(nd) = Θ(n2)

5 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a = 1b =

2

d =

2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 1 < 22, case 1 applies.

Thus we conclude that

T (n) ∈ Θ(nd) = Θ(n2)

6 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a = 1b = 2d =

2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 1 < 22, case 1 applies.

Thus we conclude that

T (n) ∈ Θ(nd) = Θ(n2)

7 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a = 1b = 2d = 2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 1 < 22, case 1 applies.

Thus we conclude that

T (n) ∈ Θ(nd) = Θ(n2)

8 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a = 1b = 2d = 2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Değerler yerleştiğinde 1 < 22,Durum 1 .

Thus we conclude that

T (n) ∈ Θ(nd) = Θ(n2)

9 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 1

T (n) = T(

n2

)+ 1

2n2 + n. Parametreler nelerdir?

a = 1b = 2d = 2

Bu parametrelere bağlı olarak hangi durum sağlanır?Değerler yerleştiğinde 1 < 22,Durum 1 .

T (n) ∈ Θ(nd) = Θ(n2)

10 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a =

2

b =

4

d =

12

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 2 = 412 , case 2 applies.

Thus we conclude that

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

11 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a = 2b =

4

d =

12

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 2 = 412 , case 2 applies.

Thus we conclude that

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

12 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a = 2b = 4d =

12

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 2 = 412 , case 2 applies.

Thus we conclude that

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

13 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a = 2b = 4d = 1

2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 2 = 412 , case 2 applies.

Thus we conclude that

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

14 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a = 2b = 4d = 1

2

Bu parametrelere bağlı olarak hangi durum sağlanır?Değerler yerleştiğinde 2 = 41/2 Durum 1.

Thus we conclude that

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

15 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 2

T (n) = 2T(

n4

)+ √

n + 42. Parametreler nelerdir?

a = 2b = 4d = 1

2

Bu parametrelere bağlı olarak hangi durum sağlanır?

Öyleyse sonuç

T (n) ∈ Θ(nd log n) = Θ(√

n log n)

16 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a =

3

b =

2

d =

1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 3 > 21, case 3 applies. Thus we conclude that

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

17 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b =

2

d =

1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 3 > 21, case 3 applies. Thus we conclude that

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

18 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b = 2d =

1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 3 > 21, case 3 applies. Thus we conclude that

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

19 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b = 2d = 1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Since 3 > 21, case 3 applies. Thus we conclude that

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

20 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b = 2d = 1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Değerler yerleştiğinde 3 > 21 Durum 3.

Thus we conclude that

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

21 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b = 2d = 1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Değerler yerleştiğinde 3 > 21 Durum 3. Öyleyse sonuç.

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Note that log2 3 ≈ 1.5849 . . .. Can we say thatT (n) ∈ Θ(n1.5849) ?

22 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

Master TeoremÖrnek 3

T (n) = 3T(

n2

)+ 3

4n + 1. Parametreler nelerdir?

a = 3b = 2d = 1

Bu parametrelere bağlı olarak hangi durum sağlanır?

Değerler yerleştiğinde 3 > 21 Durum 3. Öyleyse sonuç.

T (n) ∈ Θ(nlogb a) = Θ(nlog2 3)

Burada log2 3 ≈ 1.5849 . . ..ise aşağıdaki ifade doğru mudur?T (n) ∈ Θ(n1.5849) ?

23 / 25

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

4. Durum

f (n) (rekursif olmayan maliyet) polinomial olmadığında Master Teorem i kullanamadığımızı hatırlayalım.

Master Teoremin özel bir 4. durumu bize polilogaritmik fonksiyonları ele alma konusunda imkan sağlar.

logb a logk n) for some k ≥ 0 thenIf f (n) ∈ Θ(n

T (n) ∈ Θ(nlogb a logk+1 n)

Bu özel durum çok az rastlanan bir özelliktir.

24 / 25

Açıklama

Master Teorem

Giriş

Koşullar

Örnekler

4. Durum

4. DurumÖrnek

Aşağıdaki gibi bir rekurans bağıntımız olduğunu düşünelimn

2

)T (n) = 2T

( + n log n

Burada a = 2, b = 2, fakat f (n) polinomial değildir. Ancak

f(n) ∈ Θ(n log n)

k = 1 için "Master Teorem" in 4.durumuna göre ;

T (n) ∈ Θ(n log2 n)

25 / 25