www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Komplexität & Berechenbarkeit" - Laufzeitfunktionsbestimmung
Laufzeitfunktionsbestimmung < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Laufzeitfunktionsbestimmung: Algorithmuslaufzeit bestimmen
Status: (Frage) beantwortet Status 
Datum: 06:59 Do 19.06.2014
Autor: OominnioO

Aufgabe
Gegeben sei folgender Algorithmus:

int A(int n)
{
  int i, k;
  i=n;
  k=0;
  while(i > 0)
  {
    k=k+1;
    i=i-3;
  }
  return k;
}

a) Bestimmen Sie die Werte von A und T(n) für die Werte n=-1,0,1,2,3,6,9,30.
b) Was berechnet der Algorithmus? Begründung.
c) Bestimmen Sie den Laufzeitaufwand T(n) und begründen die Aufwandsklasse des Algorithmus A.

Hinweis: Als dominante Operation wählen Sie die Anzahl der Vergleiche.

So Hallo.

Ich hoffe, ich hab das richtige Unterforum erwischt.

Also ich hab bezüglich der obig gestellten Aufgabenstellung leider arge Probleme. Ich dachte echt ich hätte es verstanden, wie ich vorgehe bei der Bestimmung von T(n). Also bin ich dann so vorgegangen, dass ich alles was nicht vergleich war mal ignoriert habe(also wegen der dominanten Operation) und hab im endeffekt mir nur alle im while angeschaut.
Da fing das Desaster dann an. Ich hab überlegt, wie lange die Schleife läuft. Da am Ende von ihr i=i-3 gesetzt wird, dachte ich mir "Mhmmm dann muss doch bei while O(n+3) sein".
Naja hingeschrieben. dann hab ich für die andren beiden Zeilen also Setzung von K k und i jeweils O(1) angenommen. Nun bin ich erstmal ewig am Überlegen gewesen, ob ich das was in der Schleife ist nun mit der While Zeile addieren oder multiplizieren muss.

Also bin ich da gescheitert. Mein Professor hat mittlerweile die Lösungen online gestellt, aber leider typisch für ihn keinen Weg mit angegeben.

Die Lösung soll sein T(n)= (n/3)+1

Wie zum Henker kommt man dadrauf? Ich versteh das eifnach nicht. Auch wie man generell bei der Laufzeitfunktion nen Bruch drin haben kann. Leider ist mein Professor nicht wirklich gut darin zu erklären. Is echt ein netter Typ aber dazu leider nicht sonderlich gut geeignet und im Kurs konnte mir bisher auch niemand wirklich genau meinen Fehler erklären. Irgendwo muss grundlegend was falsch sein bei mir.
Die b die hab ich hinbekommen und das mit den Werten von A auch. Das war ja auch nicht sonderlich schwer.
Aber die Laufzeitfunktion amcht mir generell Probleme. Mittlerweile bekomm ich zumindest bei gegebener Funktion die Aufwandsklassen hin aber ohne Funktion kann ich glaube bei der Klausur bald auch nix ausrichten.

Wäre echt super, wenn man mir hier helfen könnte. Im Forum hab ich schon bissl geschaut und da waren teilweise ähnlcihe Fragen bei, aber leider haben die mir nicht geholfen, mein Problem zu lösen.

Freu mich auf Antworten

Liebe Grüße minni

PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.

        
Bezug
Laufzeitfunktionsbestimmung: Antwort
Status: (Antwort) fertig Status 
Datum: 09:15 Do 19.06.2014
Autor: schotti

der schleifenindex i beginnt ja mit dem startwert n und nimmt dann pro schleifendurchgang um 3 ab. im wesentlichen wird die schleife also n/3-mal durchlaufen. etwas genauer: der vergleich i > 0 fällt ceil(n/3)-mal true aus, und einmal liefert er false. wenn's nur auf die anzahl vergleiche ankommen soll, dann ist die also ceil(n/3)+1.

Bezug
                
Bezug
Laufzeitfunktionsbestimmung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 10:02 Do 19.06.2014
Autor: OominnioO

Hi

Danke für die echt sehr schnelle Antwort :-)
Also warum "+1" hab ich nun echt verstanden, ist ja irwie auch logisch wie du das erklärst. Aber warum teilt man durch 3?
Ich hätte nun wirklich 3 addiert weil ja am ende wie du auch sagtest i=i-3 gerechnet wird. Hab das dann auch gemacht und war dann von der Lösung total verwirrt.

Magst du mir das bitte erklären?

Vielen dank für deine Mühe

Bezug
                        
Bezug
Laufzeitfunktionsbestimmung: Antwort
Status: (Antwort) fertig Status 
Datum: 22:15 Mo 07.07.2014
Autor: felixf

Moin!

> Danke für die echt sehr schnelle Antwort :-)
>  Also warum "+1" hab ich nun echt verstanden, ist ja irwie
> auch logisch wie du das erklärst. Aber warum teilt man
> durch 3?
>  Ich hätte nun wirklich 3 addiert weil ja am ende wie du
> auch sagtest i=i-3 gerechnet wird. Hab das dann auch
> gemacht und war dann von der Lösung total verwirrt.

Es wird doch von $i$ solange 3 abgezogen, bis $i$ nicht mehr $> 0$ ist.

Wenn du wissen willst, wie oft du von einer Zahl $n$ die Zahl 3 abziehen kannst bis nichts mehr da ist (bzw. bis das Ergebnis negativ ist), dann ist das doch in etwa $n/3$, oder? :)

LG Felix


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Komplexität & Berechenbarkeit"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]