3. Master Theorem C++ Pseudocode / kleines Problem?

Master Theorem C++ Pseudocode / kleines Problem?

  • M

    Ich habe zwei Fragen (Master Theorem) bekommen:

    1. "Geben Sie ein Programm in C++ artigem Pseudocode an, dessen Aufwand von der Ordnung Ω(n) und O(n2), aber nicht von der Ordnung Θ(n) oder Θ(n2) ist."

    A:
    Da reicht zu schreiben:

    Meine Untergrenze ist n, meine Obergrenze n^2, somit wäre z.B. n log n eine Möglichkeit.

    for(i=0; i<n;i++) {
    ..for(i=0; i<n;i=i*2) { }
    }

    Braucht man hier noch etwas?
    (Hier gibt es noch eine Variante mit "von der Ordnung Ω(logn) und O(n2), aber nicht von der Ordnung Θ(logn) oder Θ(n2) ist.")

    2. Geben Sie in C++ artigem Pseudocode eine rekursive Funktion an, deren Laufzeitordnung Θ(n4logn) ist.
    Zeigen Sie mit Hilfe des Mastertheorems, dass Ihre Funktion wirklich die geforderte Laufzeitordnung hat.

    void doing (int i, int digit){
    if ;
    for (int i=0; i < n/2; ++i) todo n
    for (int ...
    }

    Hat jemand Idee was man hier schreiben soll?
    danke im voraus

    0
  • M

    mt_shu schrieb:

    Meine Untergrenze ist n, meine Obergrenze n^2, somit wäre z.B. n log n eine Möglichkeit.

    for(i=0; i<n;i++) {
    ..for(i=0; i<n;i=i*2) { }
    }

    Braucht man hier noch etwas?

    Du solltest im inneren Schleifenkörper noch was machen, was konstante Zeit benötigt. So würde ich die Laufzeit als 0 betrachten.

    Hat jemand Idee was man hier schreiben soll?
    danke im voraus

    Wie kannst du denn die Parameter beim Master-Theorem wählen, um auf die gewünschte Laufzeit zu kommen?

    0
  • M

    Michael E. schrieb:

    mt_shu schrieb:

    Meine Untergrenze ist n, meine Obergrenze n^2, somit wäre z.B. n log n eine Möglichkeit.

    for(i=0; i<n;i++) {
    ..for(i=0; i<n;i=i*2) { }
    }

    Braucht man hier noch etwas?

    Du solltest im inneren Schleifenkörper noch was machen, was konstante Zeit benötigt. So würde ich die Laufzeit als 0 betrachten.

    Hat jemand Idee was man hier schreiben soll?
    danke im voraus

    Wie kannst du denn die Parameter beim Master-Theorem wählen, um auf die gewünschte Laufzeit zu kommen?

    das war eine theoretische frage. man schreibts auf einem papier, keine laufzeit. trotzdem danke für die antwort

    0
  • M

    mt_shu schrieb:

    das war eine theoretische frage. man schreibts auf einem papier, keine laufzeit.

    Ich weiß. Was passt dir an meiner Antwort nicht?

    0
  • M

    Michael E. schrieb:

    mt_shu schrieb:

    das war eine theoretische frage. man schreibts auf einem papier, keine laufzeit.

    Ich weiß. Was passt dir an meiner Antwort nicht?

    "im inneren Schleifenkörper noch was machen"

    a)nachgefragt, es passt wie ich es geschrieben habe.

    b) versuche etwas allein zu herausfinden

    0
  • O

    mt_shu schrieb:

    das war eine theoretische frage. man schreibts auf einem papier, keine laufzeit. trotzdem danke für die antwort

    a) Was ist denn O(n^2)*O(0)? also so als theoretische Frage, auf einem Blatt Papier. Genau das war das Argument hier.

    b) es heisst "herauszufinden".

    0
  • M

    mt_shu schrieb:

    b) versuche etwas allein zu herausfinden

    Nein, ich will die Lösung mit dir erarbeiten. Meine erste Aufgabenstellung für dich ist, dir das Mastertheorem anzuschauen und Parameter zu wählen, um auf die gewünschte Laufzeitklasse zu kommen. Wie man dann einen Pseudocode findet, der zu den Parametern passt, ist der zweite Schritt.

    0
Anmelden zum Antworten