Diskussion:Effizienz (Informatik)

Was ist der genaue Unterschied zwischen Effizienz und Komplexität? Beschreibt die Effizienz den minimalen Aufwand eines Algorithmus, die Komplexität aber den generellen Aufwand eines Algorithmus? Die Abgrenzung ist nicht eindeutig.

Die Begriffe sind schon recht verwand. Effizienz ist quasi die positive Sicht und eher an den Algorithmus gebunden (man sagt "Der Algorithmus besitzt diese oder jene Effizienz". Komplexität die negative Sicht und mehr an das Problem angebunden (man sagt: "Das Problem besitzt diese oder jene Komplexität").

performan(z|ce)

aufgrund der einarbeitung von performance (Informatik) in diesen artikel [...]
ist effizienz und performance wirklich das gleiche? wenn man in google nach dem gleichzeitigen auftreten beider begriffe sucht, wird man manchmal auf dokumente stossen, die da einen unterschied sehen wollen, ihn aber nicht direkt preis geben. weiss dazu jemand naeheres?--seth 22:35, 8. Sep 2005 (CEST)

Effizienz und Performanz sind nicht das selbe! Mit der Effizienz eines Algorithmus meint man gewöhnlich seine Laufzeit/Platzbedarf in Landau-Notation. Performanz bezieht sich eher auf eine konkrete Implementation auf einer konkreten Maschine und ist damit genau das Gegenteil von dem, was mit der Landau-Notation intendiert ist. Ich weiß ja nicht, wer die Zusammenlegung veranlaßt hat, aber hat derjenige sich überhaupt mal beide Artikel durchgelesen? Wenn ja, wie erklärt derjenige sich dann die offensichtlichen Widersprüche im Artikel? --Coma 11:10, 26. Sep 2005 (CEST)

Full ACK -- D. Dÿsentrieb ⇌ 13:15, 26. Sep 2005 (CEST)

ok, der genannte unterschied deckt sich mit dem, was ich vermutete, jedoch nichts gescheites an quellen dazu gefunden hatte und deswegen nicht einfach so den "Performance (Informatik)" reanimieren wollte. ich werde den alten artikel nun also wiederherstellen und im zuge dessen auch meine erste obige frage dorthin verschieben.--seth 19:02, 26. Sep 2005 (CEST)

ahhh! oh! toll, habt ihr ja schon gemacht... :-) --seth 19:03, 26. Sep 2005 (CEST)

Zusammenlegen mit Komplexität (Informatik)

Ein Algorithmus ist genau dann effizient, wenn er eine geringe Komplexität hat. Soweit ich weiss, gibt es gar keine Formale Definition von Effizienz als Wert - es wird immer die Komplexität angegeben (man müsste sonst 1/O(n²) schreiben, etc...). Die aussage, die Komplexität beziehe sich nur auf Probleme, ist einfach falsch. Ein Beispiel:

• Die Komplexität der Sortierproblems is O(n*log(n))
• Die Komplexität des Quicksort-Algorithmus ist (im Average-Case), O(n*log(n))
• Die Komplexität des Bubblesort-Algorithmus ist, O(n²)
• Quicksort ist daher im allgemeinen effizienter als Bubblesort. Man sagt aber nicht, er habe "grössere Effizienz".
• Bubblesort ist aber für kleine Datenmengen (erfahrungsgemäss ca. n=10) und "billiger" Vertausche-Operation performanter als Quicksort, wegen des geringeren Overheads.

Ich möchte Vorschlagen, diesen Artikel mit Komplexität (Informatik) zusammenzulegen - in der jetzigen Form versucht der Effizienz-Artikel die Komplexität zu erklären, tut das aber wesentlich weniger genau und ausführlich, als der Komplexitätsartikel. Ich sehe nicht, wie man das verbessern kann, ohne alles nochmal zu erzählen.

Naja. Ich werde jetzt wenigstens mal einen Link auf die Komplexität einbauen. -- D. Dÿsentrieb ⇌ 13:15, 26. Sep 2005 (CEST)

Nachtrag: Oder man baute das hier um in eine kurze Pseudo-Begriffsklärung mit Verweisen zu Performanz (Informatik) und Komplexität (Informatik), und einer Kurzen erlärung der Beziehung bzw. Unterscheidung. Wäre vielleicht das beste... -- D. Dÿsentrieb ⇌ 13:22, 26. Sep 2005 (CEST)

Besser noch: Effizienz ist ja schon eine BKL. Da könnte man für die Informatik auf Performanz (Informatik) und Komplexität (Informatik) verweisen. Dann erübrigt sich das Klammer-Lemma. -- D. Dÿsentrieb ⇌ 13:28, 26. Sep 2005 (CEST)

Effizienz und Komplexität sind durchaus sehr verwandete Begriffe. Im Unterschied zu Komplexität betrachtet die Effizienz aber nur Algorithmen. Man würde nie sagen, dass ein ein "Problem effizient" ist. Das Problem, und deshalb habe ich den Artikel mal angelegt ist, dass in anderen Artikeln immer wieder der Begriff "effizenter Algorithmus" vorkommt. Wenn man diesen Begriff dann auf "Komplexität" linkt verwirrt das Laien. Bevor man also Effizienz und Komplexität zusammenlegt sollte man gründlich überlegen, ob man den Artikel "Komplexität" überhaupt so umarbeiten kann, dass er hinreichend schnell und gut erklärt, wass mit "effizienter Algorithmus" bezeichnet wird. Ich glaube nicht, dass dies wirklich möglich ist. --Coma 00:51, 27. Sep 2005 (CEST)

Ein Algorithmus ist effizient, wenn er in P ist - ganz einfach :) Aber ich verstehe dein Problem - ich möchte nur vermeiden, hier im Artikel nochmal alles zu haben, was bei der Komplexität schon steht. Hier sollte der Bezug, die Ähnlichkeit bzw. die Abgrenzung erläutert werden - anfänglich wurde ja Komplexität ja kaum erwähnt.

Übrigens halte ich Effizienz schon genau für das Gegenteil von Komplexität - wenn das eine hoch ist, ist das andere nidrig: x = 1/y. Auch sollte man IMHO bei der Effizienz nicht von "messen" sprechen - das, was du beschreibst, ist eine Berechnung - gemessen wird höchstens die Performance. Die Landau-Notation gibt im Übrigen immer die Komplexität an, nie die Effizienz: die Grösse der O-Klassen (und auch der Aufwand) wächst ja, wenn die Effizienz geringer wird. Das wird aus dem Text auch nicht klar...

Warum man für Berechnungsprobleme keine Effizienz angeben können soll, ist mir auch unklar. Das Beispiel des Sortierens ist doch ein Berechnungsproblem - da kann man prima die Effizienz vergleichen. -- D. Dÿsentrieb ⇌ 01:21, 27. Sep 2005 (CEST)

Zusammenlegen mit Effizienz (Algorithmus)

In der Informatik werden Algorithmen behandelt.

So, habe mal die drei Artikel Effizienz (Informatik), Komplexität (Informatik) und Effizienz (Algorithmus) als Doppeleinträge voneinander markiert, da sie mMn alle drei die Anwendung der O-Notation auf Algorithmen beschreiben, und es gut wäre wenn aus den drei Artikeln einer würde, und die anderen beiden Redirects würden. Regnaron 21:39, 5. Nov 2005 (CET)

Nochmals: Das ist nicht das selbe! Der Begriff "Komplexität" bezieht sich auf Probleme. Der Begriff "Effizienz" auf Algorithmen. --Coma 00:51, 6. Nov 2005 (CET)

Woe in der letzten Diskussion schon gesagt: der Begriff Komplexität ist durchaus auch für Algorithmen definiert. Aber das gleiche ist es nicht, die Effizienz ist umgkehrt proportional zur Komplexität (also zum Aufwand). Wie man das am besten auf die Artikel verteilt, sei mal dahingestellt, das sollte aber in irgend einer Form klar werden. Weshalb man für Berechnungsprobleme keine Effizienz angeben können soll, muss du mir auch nochmal erklären...

Wie soll ein Problem eine Effizienz besitzen? --Coma 10:15, 6. Nov 2005 (CET)

Es wird auch keine "Zeit gemessen", sondern die Anzahl der nötigen Rechenschritte (Befehle, nicht Takte) gezählt - die Anzahl der Takte hängt stark von einer realen CPU ab, während die Anzahl der Schritte in einem Algorithmus unabhängig von der Implementation ist.

Wie dem auch sei: Effizienz (Informatik) und Effizienz (Algorithmus) ist in der tat genau das selbe. -- D. Dÿsentrieb ⇌ 01:06, 6. Nov 2005 (CET)

Ja, das ist tatsächlich so... --Coma 10:15, 6. Nov 2005 (CET)

Hi! Bei Algorithmen sagst du ja selbst, dass Komplexität und Effizienz quasi dasselbe sind. (halt Effizienz ist der "Reziprokwert" der Komplexität). Das sollte mMn mit einem kleinen Nebensatz abhandelbar sein. Bei Algorithmen behauptet der Artikel Effizienz (Informatik) ja äquivalent mit der Komplexität zu sein: In der Informatik versteht man unter der Effizienz eines Algorithmus seinen Bedarf an den Ressourcen Zeit und Platz. In diesem Sinne ist der Begriff der Effizienz äquivalent zum Begriff der Komplexität eines Algorithmus Bleibt also nur noch das Kapitel Probleme vs. Algorithmen, was man mMn wiederrum in einem Satz erwähnen kann. Würde man also alle Artikel unter Komplexität zusammenfassen, wäre dieses Lemma schon einmal für alle Fälle definiert. Im Artikel kann man dann noch sagen dass Algorithmen effizient sind, genau dann wenn sie in polynomieller Zeit berechenbar sind, aber das immer noch zu langsam ist, und man die Effizienz eines Algorithmus als Reziprokwert seiner Komplexität verstehen kann. Regnaron 08:49, 6. Nov 2005 (CET)

Also ich möchte auch das mit dem Reziprokewert mal anzweifeln! Diese Behauptung reduziert den Begriff der Komplexität nämlich auf seine negative Sicht. Ich kann, wenn ich die Komplexität eines Problems oder Algortihmus angebe, aber sowohl ausdrücken, dass das Problem leicht lösbar ist, als auch, dass es schwer lösbar ist. Und egal, ob ich bei einem Algorithmus die Effizienz oder die Komplexität angebe, ich gebe die selbe Funktion an, und nicht etwa einen Reziprokwert. Genauso reduziert also auch obige Behauptung die Effizienz auf ihre positive Sichtweise.

Und jetzt noch was ganz wichtiges: Bevor die Artikel wirklich zusammengelegt werden, sollte unbedingt geprüft werden, welche Artikel auf diese Verweisen, und darüber nachgedacht werden, wie die Einleitung so formuliert werden kann, dass sich der Nutzer beim Klicken auf die Links nicht verarscht füllt. Wenn ich einen Artikel zur Effizienz erwarte und bei Komplexität lande, so würde ich mich als Laie etwas verarscht fühlen. Wenn man beides zusammenlegt, sollte der Artikel vielleicht auch "Komplexität und Effizienz in der Informatik|Komplexitätstheorie" heißen. Das würde dieses Problem möglicherweise lösen. --Coma 10:15, 6. Nov 2005 (CET)

Hm, also nachdem ich mal die Whatlinkshere Seiten schnell überflogen habe, würde ich sagen: Effizienz (Algorithmus) wird quasi gar nicht bezeigt, es wird ab und an gesagt dass es effiziente Algorithmen gibt. Effizienz (Informatik) wird scheinbar meistens im Sinne der Komplexitättheorie also Landau Notation verlinkt. (Meistens sind es Datenstrukturen die den Link verwenden) Teilweise wird es aber auch im Sinne der Algorithmik verwendet (schnelles potenzieren, wo von Effizienten Verfahren zum schnellen Potenzieren gesprochen wird) Die meisten Links gehen jedoch momentan schon auf Komplexität (Informatik). Aber gegen ein viertes Lemma was die drei bisherigen Lemmata zusammenfasst habe ich prinzipiell auch nichts. Man kann den Artikel ja auch in die beiden Unterabschnitte Effizienz und Komplexität teilen. Also wie gesagt: Momentan scheint mir dass die meisten Artikel entweder von effizienten bzw effizienteren Algorithmen sprechen, oder Dinge wie O-Notation im Kopf haben. Regnaron 11:18, 6. Nov 2005 (CET)

Also, ich versuche mal zusammenzufassen:

• Effizienz (Algorithmus) und Effizienz (Informatik) auf jeden Fall zusammenfassen.
• Zusammenhang/Abgrenzug zu Komplexität (Informatik) und Performance (Informatik) klar darstellen, Dopplung des Inhalts vermeiden.
• evtl. Zusammenlegen mit Effizienz, mit Hinweis/Abgrenzung zu Komplexität (Informatik) und Performance (Informatik).
• Das mit der "Messung der Zeit" muss dringend umgeschieben werden.

Offen ist:

• gibt es eine Formale Definition von Effizienz, i.e. lässt sie sich für einen gegebenen Algorithmus exakt angeben? Wenn ja wie?
• Falls sie genau wie die Komplexität angegeben wird, dann ist sie das selbe (selbe definition, selber wert bzw Funktionsklasse). Allerdings hätte ich gerne eine Quelle für die Behauptung.
• mMn kann eine formale definition (falls es die überhaupt gibt) nur im Kehrwert der Komplexität bestehen.

@Coma: bezüglich der Aussage, dass man für Berechnungsprobleme keine Effizienz angeben kann: du hast natürlich recht, dass man für Probleme nie ein Effizienz angeben kann - aber warum steht das Berechnungsprobleme? Das gilt doch auch für Entscheidungs- und Optimierungsprobleme, oder? Das hat mich verwirrt. -- D. Dÿsentrieb ⇌ 15:41, 6. Nov 2005 (CET)

Berechnungsprobleme sind Funktionen. Jedes Problem im Sinne der Berechenbarkeitstheorie oder der Komplexitätstheorie lässt sich als Funktion darstellen, die von den natürlichen Zahlen in eine Teilmenge der natürlichen Zahlen abbildet. Insofern sind alle Entscheidungs- und Optimierungsprobleme Berechnungsprobleme und als solche Spezialfälle davon. --Coma 08:58, 7. Nov 2005 (CET)

Also, das kenne ich anders:

• Berechnungsproblem: finde eine gültige Lösung x für Problem P (also ein wort w in L)
• Entscheidungsproblem: bestime, ob x eine gültige Lösung für P ist (also ob w ein Wort in L ist)

Es gibt viele verschiedene Varienten sowas zu betrachten. Über Funktionenen ist eine. Über Strings eine andere. Formal kann man immer in beide Varianten abbilden und dann stellt man fest, dass ein Entscheidungsproblem immer ein Speziallfall eines Berechnungsproblems ist. Die Lösungsmenge besteht dann eben nur aus den zwei Elementen "ja" und "nein". --Coma 10:37, 8 November 2005 (CET)

Insbesondere kann das Entscheidungsprobelm für L berechenbar sein, auch wenn es das Berechnungsproblem nicht ist, weil die Lösungsmenge unendlich ist. Aber davon abgesehen - wenn man deiner definition folgt, was ist dann der unterschied zwischen Problem und Berechnungsproblem? Alle Probleme sind dann Berechnungsprobleme, es macht keinen Sinn, das dazuzusagen.

Ob ein Problem berechenbar ist, hat nichts mit der Größe der Lösungsmenge zu tun. Auch Entscheidungsprobleme können nicht berechnbar sein (in dem Fall sagt man dann unentscheidbar). Es gibt da keinen Unterschied in diesem Kontext zwischen Problem und Berechnungsproblem. Man sollte dennoch den zweiten Begriff verwenden, weil es ja noch Probleme außerhalb dieses Kontextes gibt. --Coma 10:37, 8 November 2005 (CET)

Aber all das hilft uns ja beim Zusammenlegen der Artikel nicht weiter... kannst du zu meiner Zusammenfassung oben noch was sagen? -- D. Dÿsentrieb ⇌ 14:05, 7. Nov 2005 (CET)

Im wesentlichen Stimme ich dir zu. Effizienz und Komplexität sollten nur unter einem neuen Lemma zusammegelegt werden, das beide Begriffe im Titel nennt. Effizenz wird so normalerweise nicht definiert. Man definiert eher das Wort "effizent"="in polynomialzeit", aber das ist ein Adjektiv und sollte nicht als Lemma benutzt werden, daher der Tückgriff auf Effizenz. (du wirst häufig sehen, dass das Wort "effizent" auf "Effizienz (XXX)" verlinkt ist. Allerdings wird "effizient" in verschiedenen Kontexten auch anderes definiert oder informal benutzt, beispielsweise in Bezug auf bisherige bekannte Algorithmen zur Lösung einen Problems. Da kann dann auch ein polynommieller Algorithmus ineffizent und (bei einem anderen Problem) ein exponentieller effizient sein (z.B. weil man weiß, dass es unter P!=NP keinen polynomiellen Algorithmus geben kann). --Coma 10:37, 8 November 2005 (CET)

Zusammenlegen beginnt

Liebe Leute,
habe aufmerksam eure Diskussion oberhalb gelesen und werde versuchen Effizenz (Algorithmus) und Effizienz (Informatik) hier in Effizienz (Informatik) zusammenlegen. Conny 17:33, 2. Dez 2005 (CET).