Was ist ein optimaler Algorithmus?
Hallo,
Ich suche momentan nach der Begriffsklärung für die Eigenschaft "optimal" in Bezug auf Algorithmen. Ich kann die antwort leider nur zum Beispiel in dieser Form finden:
Unter der Zeitkomplexität eines Problems wird in der Datenverarbeitung die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe. (Von Wikipedia)
Da steht aber nirgends was denn nun Optimal bedeutet. Weiß das jemand?
6 Antworten
In diesem Zusammenhang ist ein Algorithmus besser als ein anderer, wenn er weniger Rechenschritte braucht. Optimal ist der, der die wenigsten Schritte braucht.
Bei der Speicherkomplexität ist der Maßstab nicht die Anzahl der Rechenschritte, sondern der benötigte Speicherplatz. Da ist dann der Algorithmus optimal, der den wenigsten Platz braucht.
Da gebe ich Dir recht: Der Artikel setzt stillschweigend voraus, dass man mit der "Zeitkomplexität eines Algorithmus" vertraut ist.
Aber dann könnte man auch einfacher sagen:
Zeitkomplexität eines Problems := kleinste/optimale Zeitkomplexität eines Algorithmus für dieses Problem.
So gesehen heißt es genau das, was da in Wikipedia steht =D
Ein kleines Beispiel: sagen wir mal ein Algorithmus soll dir die Zahlen 1-10 ausgeben. Dann hättest du einmal die Variante, 10 Ausgaben zu schreiben mit der jeweiligen Zahl, oder du machst das als Schleife, die nach jeder Ausgabe "+1" macht. Dadurch wird - grade bei einem langen code - sehr viel eingespart, auch was Speicherplatz des Programmes angeht.
Genau so, wie man hier durch zusammenfassen Speicherkapazität spart kann man auch Rechenschritte sparen.
Ein optimaler Algorithmus hat eigentlich sogar beide Optimierungen eingehalten
Das ist einfacher anhand eines Negativbeispiels zu erklären.
Sehr viele Probleme lassen sich lösen, indem man alle Konstellationen durchspielt.
Nimm zum Beispiel ein Sudoku. Du kannst in jedes Kästchen alle Zahlen von 1 bis 9 eintragen und irgendwann erhältst du ein Sudoku, dass genau auf deine Eingangsdaten passt.
Das ist aber viel aufwändiger, als zwischendurch das Sudoku auf Plausibilität zu prüfen und ein Kästchen gar nicht mehr anzupassen, wenn die komplette Zeile / Spalte / Unterquadrat sowieso schon ungültig ist.
Es gibt also bessere Algorithmen.
Ein optimaler Algorithmus ist einer, der bezüglich der Rechenschritte (durchschnittlichen, maximal oder minimal benötigten weiß ich gerade nicht) am wenigsten benötigt. Es lässt sich keinen besseren finden.
Gemeint ist vermutlich ein asymptotisch optimaler Algorithmus. Diesen Fachausdruck gibt es.
https://en.wikipedia.org/wiki/Asymptotically_optimal_algorithm
Das Wort optimal steht für bestmöglich, macht aber nur Sinn relativ zu vorher festgelegten Eigenschaften.
Ein optimaler Algorithmus ist - in meinen Augen - einer, der
- gut verständlich ist
- und mit weniger CPU-Zyklen als andere, aber zu ihm äquivalente, Algorithmen erreicht, was er erreichen soll.
Die Eigenschaften also, die ich hiermit meiner Beurteilung zugrunde lege, sind Verständlichkeit und Effizienz.
Sie zu wählen liegt nahe, ist aber keineswegs zwingend. In der numerischen Mathematik oder für Ingenieure ist oft die Genauigkeit der Ergebnisse, die ein gewählte Algorithmus liefert, noch viel wichtiger (einfach deswegen, weil zu ungenaue Ergebnisse wertlos sein können).
Auch ob man Verständlichkeit und Effizienz als wichtige Eigenschaften einstuft, oder nur Effizienz, kann einen großen Unterschied machen: Code nämlich, der besonders effizient arbeitet, ist oft - genau deswegen - schwer zu verstehen (und deswegen zu wenig wartungsfreundlich).
Hinzu kommt: Wo uns nicht nur eine Eigenschaft wichtig ist, muss zudem noch festgelegt sein, mit welchem Gewicht jede der wichtigen Eigenschaften in die Beurteilung eingehen soll.
Du siehst also: Das Wort optimal kann recht unterschiedliche Bedeutung haben. Du selbst musst sie festlegen.
Achso das heißt man meint dann immer in einer gewissen hinsicht ist er optimal und es lässt sich kein Besserer finden. Also müsste man jetzt wieder dem bösen Mathematiker "Du du du!" sagen der einfach von Optimal spricht aber nicht sagt in welcher hinsicht, oder?