Splitt-og-hersk-algoritme

[Gjest]

Hei.
Har litt problemer med denne oppgaven. Noen som har noen forslag på hvordan den skal løses?

Tidskompleksiteten til en splitt-og-hersk-algoritme kan modelleres ved
T(n) = 2T(n/2)+n og T(2) = 1.
Gi et best mulig O-estimat for denne tidskomleksiteten.

På forhand takk

[Solar Plexsus]

Bruker du formelen

(1) T(n) = 2*T(n/2) + n

med T(2) = 1, får du at

T(2[sup]2[/sup]) = 2*T(2) + 4 = 2*1 + 4 = 6 = 2*3,

T(2[sup]3[/sup]) = 2*T(2[sup]2[/sup]) + 2[sup]3[/sup] = 2*6 + 8 = 12 + 8 = 20 = 2[sup]2[/sup]*5,

T(2[sup]4[/sup]) = 2*T(2[sup]3[/sup]) + 2[sup]4[/sup] = 2*20 + 16 = 40 + 16 = 56 = 2[sup]3[/sup]*7,

T(2[sup]5[/sup]) = 2*T(2[sup]4[/sup]) + 2[sup]5[/sup] = 2*56 + 32 = 112 + 32 = 144 = 2[sup]4[/sup]*9.

Vi ser at det er et mønster her. For 1 ≤ k ≤ 5 er nemlig

(2) T(2[sup]k[/sup]) = 2[sup]k-1[/sup]*(2k - 1),

som igjen gir

2*T(2[sup]k[/sup]) + 2[sup]k+1[/sup]
= 2*(2[sup]k-1[/sup]*(2k - 1)) + 2[sup]k+1[/sup]
= k*2[sup]k+1[/sup] - 2[sup]k[/sup] + 2[sup]k+1[/sup]
= k*2[sup]k+1[/sup] + 2[sup]k[/sup]
= 2[sup]k[/sup][2(k + 1) - 1]
= T(2[sup]k+1[/sup]).

Altså stemmer (2) overens med (1). Så vi har funnet en eksplisitt formel for T(n) når n = 2[sup]k[/sup] der k er et naturlig tall. Dette kan vi bruke til å finne en formel for T(n) som gjelder for alle n ≥ 2. Identiteten n = 2[sup]k[/sup]gir k = lnn/ln2, så

(3) T(n) = 2[sup]k-1[/sup]*(2k - 1) = (n/2)*(2*lnn/ln2 - 1) = n*lnn/ln2 - n/2.

Herav følger at

2*T(n/2) + n
= 2*[(n/2)*ln(n/2)/ln2 - n/4] + n
= n*(lnn - ln2)/ln2 - n/2 + n
= n*lnn/ln2 - n - n/2 + n
= n*lnn/ln2 - n/2.

M.a.o. tilfredsstiller formelen (3) for T(n) funksjonallikningen (1). Herav følger at

T(n)/[n*lnn] = 1/ln2 - 1/(2*lnn) < 1/ln2.

M.a.o. er

O(T(n)) = n*lnn.

[Guest]

Takk skal du ha Solar Plexus

[Guest]

Takk skal du ha Solar Plexus

Skulle nok være Solar Plexsus