Laufzeitbestimmung & Master-Theorem

elmanuel

Hallo liebe Gemeinde!

Ich hätte da mal folgendes Anliegen:

(es handelt sich nur um PSEUDOcode)

1.frage zum mastertheorem:

programm(n)

for(;i<n;i++)
{
if(worst case) programm(n/2);
cout << "hello world";
}

hätte ich dann im worst case

a=1 wegen 1 rekursiver aufruf
b=2 wegen problem halbiert sich
c=1 wegen n^1=n

⇒ logb(a)=log(a)/log(b)=0<c
⇒ fall c<logb(a)
⇒ T(n)=theta(n^c)=theta(n)

also hat das programm im schlechtesten fall noch immer

aufwand n?? wie kann das sein??

2.abschätzung schleifen-programm:

programm(n)

for(;i<n;i++)
{
if(worst case)
for(;i<n;i++)
cout << "i'm bad";

cout << "hello world";
}

innere schleifen multiplizieren sich
also aufwand im worst case aufwand n^2 also O(n^2)
im best case aufwand n also omega(n)

theta(n) existiert nicht da omega(n) ungleich O(n^2)

richtig so?

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

elmanuel

wenn keiner antwortet nehme ich an das es richtig ist was ich geschrieben habe

elmanuel schrieb:

a=1 wegen 1 rekursiver aufruf

Ich sehe da n rekursive Aufrufe.

SeppJ

elmanuel schrieb:

wenn keiner antwortet nehme ich an das es richtig ist was ich geschrieben habe

Das kann auch heißen, die Frage ist unlesbar oder unverständlich. Für beides, ganz besondere das erstere, gibt es bei deinem Beitrag starke Anzeichen.

elmanuel

qweewrertertert schrieb:

elmanuel schrieb:

a=1 wegen 1 rekursiver aufruf

Ich sehe da n rekursive Aufrufe.

ja ... also es geht ja um das master-theorem. da ist ja die anzahl der rekursionen relevant ... also meinst du wenn ich a=1 erzeugen möchte müsste die rekursion außerhalb der schleife stehen?

elmanuel

programm(n) 
{

  for(;i<n;i++) 
  { 
    cout << "hello world"; 
  } 

  if(worst case) programm(n/2); 
}

hätte ich dann im worst case

a=1 wegen 1 rekursiver aufruf
b=2 wegen problem halbiert sich
c=1 wegen n^1=n

⇒ logb(a)=log(a)/log(b)=0<c
⇒ fall c<logb(a)
⇒ T(n)=theta(n^c)=theta(n)

also hat das programm im schlechtesten fall noch immer

aufwand n?? wie kann das sein??

Christoph

elmanuel schrieb:

aufwand n?? wie kann das sein??

n + n/2 + n/4 + ... ist höchstens 2n und damit in O(n).

elmanuel

Verstehe, Danke Christoph!

und wie sieht es mit fall 2. aus

abschätzung schleifen-programm:

programm(n) 
{
  for(int i=0;i<n;i++) 
  { 
    if(worst case) 
      for(int j=0;i<n;++j) 
        cout << "i'm bad"; 

    cout << "hello world"; 
  }
}

innere schleifen multiplizieren sich
also aufwand im worst case aufwand n^2 also O(n^2)
im best case aufwand n also omega(n)

theta(n) existiert nicht da omega(n) ungleich O(n^2)

richtig so?

elmanuel

hab noch ein Bsp:

Bsp3. master theorem:

gewünschter aufwand: n^4 log(n)

fall c=logb(a)
c=4
=> loga/logb=4
b=2
=> a=16

programm(n)
{
  for(int i=0;i<n^4;++i)
    cout << "Hello";

  for(int i=0;i<16; ++i)
  programm(n/2);

}

korrekt?

Laufzeitbestimmung &amp; Master-Theorem

Laufzeitbestimmung & Master-Theorem