Algorithmusbewertung eines sich ändernden Zyklus |
| 17.11.2011, 14:29 | Dasiggo | Auf diesen Beitrag antworten » | ||||||
| Algorithmusbewertung eines sich ändernden Zyklus ich hoffe ich bin hier irgendwie richtig mit meinem Thema. Es geht um O Notationen. Ich habe gesehen, das hier zu diesem Thema auch Fragen gestellt werden, da wollte ich mich einreihen. Ich bin mir nicht sicher, wie ich ein Programmstück bewerten soll, bei dem sich die Abbruchbedingung ständig ändert. Konkreter geht es um eine quadratische Matrix(eigentlich ein Kandidat), die wird aber nicht komplett verarbeitet, sondern nur zum Teil bzw. werden einige Teilmatrizen bearbeitet. Wie soll so ein Algorithmus bewertet werden? Soll man so tun als ob alle Elemente bearbeitet werden, also ? Kann mir jemand folgen? 
|
||||||||
| 17.11.2011, 21:24 | Abakus | Auf diesen Beitrag antworten » | ||||||
| RE: Algorithmusbewertung eines sich ändernden Zyklus Hallo, du sprichst von der Speicherplatzkomplexität? Entweder guckt du exakt, wieviel gebraucht wird oder du schätzt es geeignet ab (worst-case usw.). Abakus 
|
||||||||
| 18.11.2011, 14:09 | Dasiggo | Auf diesen Beitrag antworten » | ||||||
Danke für die Antwort. Unter Speicherplatzkomplexität kenne ich die O-Notation nicht, aber wahrscheinlich meinst du das gleiche wie ich. Ich kenne es als Algorithmusbewertung, die aussagt wie komplex ein Algorithmus ist bzw. wie aufwendig er ist. Ich will etwas ausführlicher werden um Missverständnisse auszuschließen: So etwas wie eine Matrixbearbeitung kann ja so aussehen: for(i=0;i<n;i++) for(j=0;j<n;i++) tue_was; hier hat ja der Algorithmus die Komplexität T(n)=n^2 wenn jetzt aber n durch irgendwelche zwischen schritte verändert wird n_änderung; for(i=0;i<n;i++) n_änderung; for(j=0;j<n;i++) tue_was; Worst-case wäre hier ja n=n < also n ändert sich nicht T(n)=n^2 Umgekehrt sieht es für n=1 aus, da ist die Komplexität T(n)=1 Da ich unmöglich voraussehen kann wie n aussehen wird, nach dem Programmstart, bzw. nur mit sehr viel mühe, soll ich also lieber den obigen worst-case nehmen, also T(n)=n^2 ? |
||||||||
| 20.11.2011, 09:42 | Abakus | Auf diesen Beitrag antworten » | ||||||
Ja, wie misst du diese Komplexität denn? Das solltest du schon genauestens (!) wissen. Möglich wäre zB auch Zeitkomplexität, was oft betrachtet wird.
Also Zeitkomplexität? Du machst tue_was n^2 mal.
Nein, nützt ja nichts n zu nehmen, weil das i ja schlimmstenfalls so verändert werden könnte, dass du sogar eine Endlosschleife hast (mache i-- dort). Du musst schon genauer schauen, was da mit dem Schleifenindex passiert. Abakus
|
||||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
