Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Mastertheorem mit Logarithmus in der Summe
Hallo!
Ich habe bisher aus Schönigs Buch “Algorithmik” das Mastertheorem benutzt. klappte auch immer wunderbar.
Wie würdet ihr mit dem Mastertheorem die Komplexität für die Rekursion
T(n) = 2*T(1/2 *n) + log ( n )
finden? Laut strehlschem Skript muss rauskommen, T(n) ist element Tetta von n.
Wär nett, wenn ihr mir da helfen könntet - hatte eigentlich gedacht, ich kann das blöde thorem.
Danke und Gruß,
Marco
nein. es muss rauskommen T(n) ∈ Tetta((log(n))^2).
mann muss die Rekursion auflösen dann kommt es raus
ja, aber wie geht es ohne Aufloesen der Rekursion? denn mit Master Theorem han ich auch Tetta n bekommen und mit Aufloesen der Rekursion Tetta (logn)(logn)
dime. kannst du mir sagen, wie du auf tetta (n) kommst?
mit dem Master Theorem, ich vergleiche n^logb(a) mit f(n) (in dem Fall logn) und da, n grosser ist als logn, folgt Tetta (n)
log(n) ∈ Tett(n) => log(n) ≤cn,
hast du auch so gemacht
hmm… danke. der strehl hat das etwas anders gemacht, habs mir nochmal angeschaut. Habs aber zur hälfte verstanden (-;
thx
Marco
das master theorem, mal kurz zamm gefasst:
T(n) = a * T(n/b) + c * g(n)
so gilt:
a < g(b) => T(n) ∈ dedda( g(n) )
a = g(b) => T(n) ∈ dedda( g(n) log(n) )
a > g(b) => T(n) ∈ dedda( n^log_a(b) )
a ist hier 2
b auch
c is wurschd g(n) = log(n). das ist in der komplexitaet meist zur basis 2, also im normalfall.
g(b) ist hier 1 da 2^1 = 2
damit ist a > g(b)
daraus folgt: T(n) waechst wie n^log_2(2)
also wie n
vergesse nicht, dass Du die drei Gleichungen fuer a und b benutzen darfst, nur wenn f(n)=cn ist (also linear), und bei der Gleichung von T(n) ist f(n)=logn, d.h man darf nur den Master Therem benutzen und nicht die drei Gleichungen.
Gruss,
Dime
vielen dank an euch beide, es wird klarer.
dime, ich habe deine erläuterungen nicht ganz verstanden. darf ich nun die gleichungen verwenden oder nicht? log n ist doch nicht linear.
Gruß,
Marco
aslo in dem Fall glaube ich net, die Gleichung darfst du verwenden, nur wenn f(n) linear ist, ansonsten immer Master Theorem anwenden.
Gruss,
Dime
T(n) = T(n/2) + clog(n)
man ersetzt jetzt n = 2^k
→ k = log(n)
tk = (tk-1) + ck
tk-1 = (tk-2) + c(k-1)
.
.
.
t1 = t0 + c1
einsetzen der folgen ineinander bringt
c (k + (k-1) + (k-2) + … + 1) = c k(k+1)/2 elem Theta(k^2)
da aber k = log(n) => T(n) elem Theta(log(n)^2)
ahso, jetzt versteh ich langsam. Die Gleichungen von denen ihr redet sind nicht die des Master-Theorems. Es gibt Gleichungen, mit denen man Rekursionen löst, wenn f(n) linear ist und das Mastertheorem (auch gleichungen) mit denen man die Rekursion löst, falls f(n) nicht linear ist. Für en Fall f(n)=log(n) ist es ja nicht linear, also muss ich das Mastertheorem verwenden… man oh man… beim Schöning steht das Mastertheorem irgendwie anders drin (-: aber man sollte sich wohl an den strehl halten.
Labro: Deine Rekursion versteh ich nicht. wenn du n=2^k setzt dann musst du doch auch T(2^k) = 2*T(2^(k-1)) + k setzen … oder nicht?
Gruß,
Marco
Aber es heißt doch 2*T(n/2) + log(n).
ja wenn es hieße T(n) = 2T(n/2) +clog(n)
es steht aber hier T(n) = T(n/2) +c*log(n)
weiss nicht wo die aufgabe genau steht, aber beim Strehl im tutorium war die zumindest so gestellt
@ML
genau, jetzt hast du es richtig 
Gruss,
Dime
kennt sich jeman von euch bei der Auf 23 aus:
Warum hat man da Auswahl zwischen die beiden möglichkeiten (2,2,2,2) und (1,2,3,3)?
a) weil nur die beiden Längen die Bed. N*logN <= h(t) < (N^2 + N - 2)/2 erfüllen und mind. 2 Elemente müssen auf gleicher Höhe liegen (Huffman def. )? stimmt das?
b)wann ist (1,2,3,3,) besser als (2,2,2,2) ?
wenn p3+p4 > p1 ? denn dann wird die Bin.Baum von 1,2,3,3, in 2,2,2,2 umgabaut (wegen Huffmann) ? stimmt das?
da bin ich mir net so sicher, ob ich die Aufgabe richtig geloest hab, und Antworten hab ich auch nicht.
Danke
Was willst du uns damit sagen? ich verstehe es nicht. Was ist dann DEINER Ansicht nach das Master Theorem? wenn du mal bei Wikipedia nachguckst und das ein bissl ummodelst ist das ziemlich genau die 3 Gleichungen.
Wo kann ich nachlesen, dass f polynomial sein muss, damit das gilt? ich hab bis jetzt nichts dazu gefunden, also HILFE
ich hab deinen Beitrag schnell durchgelesen und hab mir gedacht, du betrachtest die Faelle, wenn f(n) linear ist, aber das was du geschrieben hast ist auch richtig. Ich hab Master Theorem vom Buch gelesen und da gibts auch die drei Gleichungen mit a<b, a=b und a>b und dementsprechende Tettas aber die gelten nur wenn f(n)=cn also linear.
sorry fuer die Umstaende
kennst du Dich aus bei der Auf 23?