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
Splitt-og-hersk-algoritme
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Over-Guru
- Innlegg: 1685
- Registrert: 03/10-2005 12:09
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.
(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.