Diskussion:Zeitkomplexität

Erste Kommentare

Unter der Zeitkomplexität eines Problems versteht man die (minimale) Anzahl an Rechenschritten, ... Also das halte ich für ein Gerücht. Ein Algorithmus braucht für n Aktionen immer mindestens O(1), ob er nun etwas tut oder nicht. Steht - zumindest in der Informatik - O nicht eher für die maximale Anzahl? --Bodo Thiesen 06:24, 14. Dez 2004 (CET)

Wie schaffst Du denn n Aktionen in O(1)? Selbst wenn jede dieser Aktionen in konstanter Zeit (also O(1)) machbar ist, brauchst Du $n\cdot O(1)=O(n)$ für n Aktionen. Mit der O-Notation wird in der Informatik eine Funktion angegeben, die mindestens genauso stark wächst, wie das, was man abschätzen möchte (in diesem Fall also die Laufzeit Deines Algorithmus). Siehe auch Landau-Symbole. --Pinguin.tk 13:54, 14. Dez 2004 (CET)

int fake_strlen(char * string) { return 42; }

Laufzeitkomplexität? Richtig, O(1) und nicht O(n). Jeder Algorithmus ist mindestens O(1). Die meisten sind selbstverständlich komplexer, aber O(1) ist jeder (mindestens). Und die Formulierung von oben interpretiere ich so, daß ich einfach für einen gegebenen Algorithmus sage "Jo, der beaucht mindestens Zeit für Pro- und Epilog, und macht dann auch noch irgendwas, also ist er mindestens O(1)", und kann dann diesen Algorithmus ohne weitere Betrachtung als O(1) einstufen. Das ist selbstverständlich nicht richtig, aber das ist die Aussage des Satzes. Ich meine, es wäre die "maximale" Anzahl an Operationen, die O angibt, nicht die Minimale. --Bodo Thiesen 08:16, 17. Dez 2004 (CET)

Zu Deinem Algorithmus: ja, der braucht =O(1) -- was genau ist denn das Problem dabei? Er verarbeitet ja auch keine n Einträge, sondern gar nichts, er gibt schließlich unabhängig von der Eingabe 42 zurück.

Zur O-Notation: Die gibt schon eine obere Grenze an, aber es ist nicht ganz die maximale Anzahl an Operationen -- denn es handelt sich ja um eine asymptotische Notation. Nehmen wir beispielsweise Quicksort, das hat als worst case $O(n^{2})$, aber meistens braucht es nur $O(n\cdot \log n)$. Also kann die tatsächlich benötigte Anzahl an Operationen natürlich geringer sein als das, was die O-Notation besagt. Allerdings braucht der Algorithmus im schlechtesten Fall vermutlich nicht exakt $n^{2}$ Schritte, sondern vielleicht $3\cdot n^{2}+15$ oder sonst etwas krummes. Diese Faktoren ändern sich je nach Implementierung und Maschine, und wenn man n beliebig groß werden lässt, sind die +15 und auch die 3 uninteressant, sie fallen nicht ins Gewicht. Deshalb gibt die O-Notation die "Wachstumsgrößenordnung" an. In gewisser Hinsicht also eine obere Grenze, in Bezug auf einen Algorithmus. Wenn man sich dagegen auf ein Problem bezieht, dann gibt man in der Regel als Komplexität an, wie "schlecht" es mit dem besten Algorithmus gelöst werden kann -- und insofern handelt es sich um eine untere Grenze! Nochmal Beispiel sortieren: Die Komplexität des Problems ist $O(n\cdot \log n)$, schneller geht's nicht (kann man in diesem schönen Fall sogar beweisen, sonst oft nicht). Das hält aber niemanden davon ab, einen Algorithmus zu entwerfen, der in $O(2^{n})$ sortiert. Dann hat dieser zwar eine hohe Anzahl von maximalen Schritten, aber das ändert nichts an der Komplexität des Problems.

Ich sehe aber ein, dass die Formulierung missverständlich ist oder man zumindest genauer ausführen sollte, wie sich Algorithmus und Problem hier unterscheiden. Hilft Dir meine Darstellung oben weiter, oder hast Du einen anderen Vorschlag? --Pinguin.tk 10:51, 17. Dez 2004 (CET)

---

So ist Bubblesort zwar für große Datenmengen ein recht langsames Verfahren, eignet sich aber aufgrund des geringen Overheads gut für kleine Datenmengen (insbesondere für n <= 8).

Das Problem ist nur, dass der Overhead und ueberhaupt das Sortierverfahren fuer n <= 8 so gut wie egal ist ... --zeno 14:25, 18. Apr 2005 (CEST)

---

Das Lemma wird auf den Begriff Zeit bezogen, im Folgenden aber mit Anzahl der Rechenschritte definiert. Da nicht alle Rechenschritte immer die gleiche Zeit benötigen müssen, kommt mir die Definition unsauber vor. Warum wird nirgends der Begriff Zeitaufwand bzw. Zeitverhalten verwendet? Dies kann ich nicht so ganz nachvollziehen.--H3xc0d3r (Diskussion) 11:04, 23. Jan. 2016 (CET)

Struktur

Ich würde sagen, dass die Struktur des Artikels überarbeitungswürdig ist und verbessert werden könnte. Zum anderen könnte ein Beispiel vorhanden sein, welches das ganze anschaulich präsentiert.--Razorhawk 01:03, 1. Feb 2006 (CET)

Fehler

Beim Fibonacciheap steht, dass "Einsortierens eines neuen Eintrags" manchmal teuer ist. Das ist doch totaler Unsinn: Insert werden immer in konstanter Zeit gemacht, denn es wird nur ein Ein-Knoten-Baum als neues Listenelement angehängt.

Verwendung des Begriffs für Algorithmen

Die im zweiten Absatz der Einleitung beschriebene Verwendung des Begriffs Zeitkomplexität für einen Algorithmus ist mir fremd. Bisher ging ich davon aus, dass Algorithmen eine Laufzeit haben und Probleme eine Zeitkomplexität. Es wäre gut, wenn diese Verwendung durch eine Quellenangabe belegt werden könnte und am besten darauf hingewiesen würde, dass damit das gleiche wie mit dem Begriff Laufzeit beschrieben wird, für den es einen eigenen Artikel gibt. --Maformatiker (Diskussion) 18:05, 4. Mai 2017 (CEST)

Das war mir im Gegensatz sogar geläufiger als die hier zuerst aufgeführte Zeitkomplexität von Problemen. Online-Quelle z.B. https://www.leda-tutorial.org/de/offiziell/ch02s02s03.html. Das sind offenbar Synonyme, wobei der Artikel Laufzeit (Informatik) wiederum mehrere Bedeutungen behandelt. Witzigerweise war in der Diskussion zum anderen Artikel jemand 2013 gerade der gegenteiligen Meinung. Aber unabhängig davon wie man das aufdröseln mag, mehr gute Quellen wären von nöten.--Jocme (Diskussion) 21:28, 26. Sep. 2019 (CEST)

Resultattabellen sparen Rechenzeit (Abkürzen unabhängiger Teilschritte)

In der Realität hat man ja niemals unendlich viel RAM. Und bezogen auf eine begrenzte Menge Speicher läßt sich jeder Algorithmus als Riesensumme von Zuordnungen Eingabe zu Resultat beziehungsweise "auf jenen Zustand folgt dieses", wobei man das Ergebnis aus einer Riesentabelle aus Zuständen entnimmt, umschreiben. Rein formell ist damit jedes Laufzeitproblem gelöst. Die optimale Laufzeit ist immer ein Rechenschritt. Das bringt zwar in der Praxis nicht viel, aber andererseits gibt es in der realen Praxis auch niemals eine unendliche Menge möglicher Eingaben. Es könnte sein, daß man erstaunlich oft bereits fertige Programmabschnitte durch solche Zustandsübergänge ersetzen und damit eine Beschleunigung erreichen kann. Sinustabellen sind nur ein Beispiel. (nicht signierter Beitrag von 2003:C6:E715:4300:ED23:4A3B:DEDD:2DBF (Diskussion) 06:05, 29. Sep. 2020 (CEST))

Ganz so einfach ist dem nicht. Wäre dem jedoch so, wäre die Wikipedia zunächst nicht der richtige Ort dafür, da die Wikipedia kein Ort für Theoriefindung ist, siehe Wikipedia:Was Wikipedia nicht ist. Falls du wissenschaftliche Quellen hast, die diesbezüglich Aussagen treffen, wäre hier jedoch der richtige Ort diese vorzubringen.--BlauerBaum (Diskussion) 12:16, 29. Sep. 2020 (CEST)

Ich glaube ebenfalls, dass der Ergebnisraum wesentlich größer ist als hier angenommen wird. Im Beispiel der Sinustabellen, so möchte man bereits bei so einem einfachen eindimensionalen Fall doch möglichst viele reelle Zahlen zwischen 0 und 1 (bzw. -1 bis 1 eigentlich, aber immerhin symmetrisch) abbilden. Davon gibt es über abzahlbar unendlich viele. Für viele physikalische Vorgänge wären 5-6 Nachkommastellen mindestens wünschenswert. (Grund: Ohne ins Detail zu gehen, können wir annehmen, dass viele Messinstrumente problemlos auf 3-4 Stellen genau sind. Ein mathematischer Algorithmus sollte somit nicht das Hindernis sein bei einer Fehlerrechnung.)D.h. wir haben bereits 10^6 Fälle, die zu 10^6 verschiedenen Outcomes führen.Das gleiche gelte für Wurzeln (und zwar alle beliebigen Wurzeln), Logs usw.

Besonders problematisch wird es, wenn eine Funktion zwei oder mehr Inputs besitzt. Dann skaliert das Problem sogar quadratisch oder kubisch.

Die Aussage, dass "rein formell" "damit jedes Laufzeitproblem gelöst" sei, ist somit etwa genauso korrekt wenn auch unbrauchbar, wie die Aussage, dass ich jede Sprache beliebig fließend sprechen könnte, wenn ich nur schnell genug in einem praktisch unendlich großen Wörter- und Grammatikbuch herumblättern kann. --FlMcc (Diskussion) 05:59, 10. Nov. 2024 (CET)