Cherrycoke

Aufgabe: In einem Heap mit n Datensätzen werde der Schlüssel eines beliebigen Datensatzes geändert. Formulieren Sie einen Algorithmus mit Aufwand O(log(n)), der die Heapstruktur wieder herstellt. (Sie müssen also auch eine Aufwandsanalyse durchführen!) Lösung: [U]Algorithmus[/U]: Heap bearbeiten [U]Eingabe[/U]: Zu bearbeitende Heap h, Schlüssel s des zu bearbeitenden Knotens, neuer Schlüssel t [U]Ausgabe[/U]: Heap h Suche Knoten n mit Schlüssel s; Wenn Knoten n mit Schlüssel s gefunden: Ersetze s durch t Sonst: Gebe aus „Zu bearbeitender Schlüssel nicht gefunden“; Beende den Algorithmus; Solange t kleiner als Schlüssel eines Sohnes von n Bestimme den größeren Schlüssel g der beiden Söhne von n; Vertausche n mit dem Sohn mit g (sift down); Solange t größer ist als Schlüssel des Vaters Vertausche t mir seinem Vater (sift up); Meine erste Frage wäre, ob der Algorithmus so korrekt ist, oder ob ich etwas vergessen habe zu ebachten? Meine zweite Frage wäre, wie ich die Aufwandsanalyse durchzuführen habe. Darin bin ich leider nicht so fit. O(log(n)) im Worstcase ist meiner Meinung nach gegeben, da ich maximal h (Höhe) Schritte durchführen kann, indem ich entweder die kleinste Zahl ganz oben einfüge, oder die größte Zahl ganz unten. Die Höhe ist ja gleich log(n). Aber wie schreibe ich das nun mathematisch korrekt auf?

Wenn ich dir jetzt richtig folgen konnte, bedeutet das, dass die iterative Fakultätfunktion eine Komplexität von O(n) hat. Habe ich das richtig verstanden? Rekursiv wäre es n*O(n), wobei n eine Konstante ist, und ich dann auch O(n) erhalte? Da muss doch ein Fehler drin sein - sonst würde das ja bedeuten, dass sowohl die iterative Variante, als auch die rekursive Variante die gleiche Laufzeit hätten? *verwirrt sei*

Wenn ich noch einmal genauer darüber nachdenke, muss die Bedingung p+1-mal überprüft werden. Aber was wäre dann die Komplexität? Ich bin jetzt total verwirrt! Wäre die Komplexität dann O(p+1)?

Hier sind meine Gedanken: Die Schleife wird p-mal durchlaufen. Vor der Schleife steht eine Zuweisung, also würde ich hier sagen 1*O(1). Für die Schleife selbst muss p-mal überprüft werden ob i <= p ist, was ein Aufwand von O(1) ist. Dann findet noch eine Zuweisung statt (i++) was auch p * O(1) entspricht. Was hätte denn f = f* i für einen Aufwand? Bisher hätte ich also 1 * O(1) + p * ( O(1) + O (1) + x). Da mich ja nur eine obere Schranke interessiert hätte ich dann p*(O(1) + x)? (x ist der Teil f = f * i, da ich nciht weiß, wie man diesen Aufwand berechnet)

Hmm, da beginnt es ja schon bei mir. *peinlich* Wie berechne ich denn die Komplexität der Fakultät in iterativer Form? Folgendes wäre ja iterativ, oder? 1! = 1 2! = 1 * 2 3! = 1 * 2 * 3 Ich habe wirklich keine Idee, wie ich denn nun die Komplexität berechne... Okay, da bei 1 nichts berechnet werden muss, würde ich für n = 1 sagen 0(1) = 1. Aber was wäre die Komplexität von n = 2?

Leider war Theorie noch nie so wirklich meine Stärke. Zur O-Notation habe ich schon einige Texte gelesen, allerdings scheitert es bei mir an der praktischen Anwendung. Also kann man für mein Beispiel sagen: T(0) = O(1) + O(1) Da bei der 0 als Eingabe Eine Zuweisung in der zweiten Zeile und eine Zuweisung in der fünften Zeile stattfindet? Aber was wäre dann T(1)? Da das Ganze rekursiv abläuft, müsste T(1) irgendwas + T(0) sein, also: T(1) = x + T(0) Aber ich verstehe nicht ganz, was die Zeile fak = fakultaet( n-1 ) * n für einen Zeitaufwand hat. Kann mir hier nochmal wer auf die Sprünge helfen?

Hallo Community, ich mache mir mein Leben noch etwas mit der O-Notation schwer. Vielleicht könnt ihr mir ja kurz weiterhelfen? Ich habe folgenden Algorithmus fakultaet( n ) gegeben: Eingabe: n ist eine natürliche Zahl Ausgabe: n! = 1 * 2 * ... mit 0! := 1 wenn n = 0 fak = 1 sonst fak = fakultaet( n-1 ) * n fakultaet = fak Nun möchte ich hierzu die Zeitkomplexität bestimmen. Folgendes habe ich mir dazu gedacht: Innerhalb einer If-Abfrage interessiert mich nur der "Teil", der Zeitintensiver ist, also in diesem Fall fak = fakultaet( n-1 ) * n. Doch hier weiß ich schon nicht mehr, wie ich den Zeitaufwand dieser Zeile bestimme. Könnte mir das jemand vielleicht kurz erklären? Vielen Dank!