msgbartop
Gruppe F1
msgbarbottom

21 Dec 08 Kleine Zusatzaufgabe zur Landau-Notation

Ich weiß nicht, wer schon alles mit der Landau-Notation vertraut ist (und auch mit der Komplexitätstheorie von Algorithmen). Aber als kleine Zusatzaufgabe´ zur Hausaufgabe vom Blatt 6 (weil ich sie gerade korrigiere) folgendes:

Welche Laufzeiten (ala O(n), etc.) hat der Primzahltest normalerweise, wenn wir ihn so programmieren wie in der Musterlösung zur 1a)?

static boolean isPrime(int p ) {
  for( int k = 2 ; k * k <= p ; k++ ) {
    if( p % k == 0 ) {
      return false;
    }
  }
  return true;
}
[/sourcecode]

Fleißaufgabe:
Wie sieht's mit den Laufzeiten der anderen Funktionen aus?

Man kann die Lösung wahrscheinlich leicht mit Google finden, aber es an sich ganz nett da selber einmal darauf zukommen.



Reader's Comments

  1. |

    du – wenn ich den algorithmus mit p = 5 durchspiele kommt doch false raus:

    die for Schleife wird 1x durchlaufen, die if Anweisung liefert “false” – folglich terminiert
    der algorithmus mit false – was ja falsch ist.

  2. |

    Err woops, habe beim Hinschreiben true und false vertauscht. Hab’s verbessert, sorry. Danke für den Hinweis :-)

  3. |

    Wieso denn nicht $$\mathcal{O}(\sqrt{n})$$ (n ist der Zahlenwert)? Wenn man annimmt, dass die Modulo-Operation in konstanter Zeit abläuft, iteriert die Schleife doch höchstens Wurzel-n mal?

  4. |

    Die Frage ist: was ist $$\mathbf{n}$$ im Allgemeinen, wenn man die Komplexität von Algorithmen untersucht?
    Würde man Algorithmen direkt nach dem Wert ihrer Parameter bewerten, wäre Deine Antwort richtig und es stimmt ja auch, dass die Schleife höchstens $$ \mathbf{\sqrt{p}} $$-mal durchläuft, also die Funktion in $$ \mathbf{\sqrt{n}} $$ vielen Schritten fertig ist – aber der Zahlenwert ist nicht das Maß in dessen Abhängigkeit gemessen wird. Bei Arrays oder mehreren Parametern könnte man zum Beispiel nicht wirklich etwas mit dem Zahlenwert als Maß anfangen.

    Computational_complexity_theory_topics
    und da Time Complexity bzw. die Fußnote im Hinweis anschauen :-)

  5. |

    Edit (Andreas):
    Glückwunsch – das ist die Lösung :-)
    Ich hab’s mal ein wenig versteckt, damit man nicht aus Versehen drüberstolpert :-)
    Eigentlich sollte es über den Comments ein kleines “e” geben – wenn man da draufklickt, kann man seine Comments editieren.



Leave a Comment

You must be logged in to post a comment.