Affenpuzzle und praktische Berechenbarkeit / Faktorisierung

Bei einer Kantenlänge von n Karten gibt es (n*n)! Möglichkeiten die Karten anzuordnen. Für jede Karte gibt es 4 Möglichkeiten diese zu drehen. Damit ergibt sich eine gesamte Zahl an (n*n)! * 4(n*n) verschiedenen Möglichkeiten. Im schlechtesten Fall müssen diese alle untersucht werden (beim naiven Algorithmus). (siehe auch inf-schule) Man könnte das Verfahren auf verschiedene… Weiterlesen Affenpuzzle und praktische Berechenbarkeit / Faktorisierung

Asymptotisches Wachstumsverhalten

Den Anfang der Stunde haben wir damit verbracht uns die unterschiedlichen Wachstumsarten noch einmal anzuschauen (http://inf-schule.de/grenzen/komplexitaet/sortieren/asymptotischesverhalten/komplexitaetsklassen ). Danach haben wir eine Komplexitätsklasse kennengelernt welche man als „O(f)“ bezeichnet. Hierunter versteht man eine Klasse aller Funktionen, die nicht schneller wachsen als eine vorgegebene (Kosten-) Funktion f. Beispiel O(f): O(n³) > l(n) = n² Hierbei gehört also die… Weiterlesen Asymptotisches Wachstumsverhalten