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. Iwan | 23 Dec 2008 12:09 am

   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. Andreas | 23 Dec 2008 12:18 am

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

3. Felix | 27 Dec 2008 1:11 am

   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. Andreas | 27 Dec 2008 10:12 am

   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. Felix | 27 Dec 2008 5:25 pm
   Richtige Lösung »

   naja ok, dann bezeichne $$\mathbf{n}$$ die Bitlänge der Zahl p ($$\mathbf{n} := \log \mathbf{p}$$), die Komplexität wäre dann:

   $$\mathcal{O}(\sqrt{2^{\log{\mathbf{p}}}}) = \mathcal{O}\left({(2^{\log{\mathbf{p}}})}^\frac12\right) = \mathcal{O}\left({(2^\frac12)}^{\log{\mathbf{p}}}\right) = \mathcal{O}\left(\sqrt{2}^\mathbf{n}\right)$$. Die Komplexität steigt also exponentiell zur Bitlänge.

   PS: War ja klar, dass es beim ersten Mal nicht klappt

   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.