Die häufigsten Fehler beim 7. Übungsblatt

Hallo!

Auch beim Korrigieren des 7. Übungsblattes sind uns wieder einige Fehler aufgefallen, deren Ausräumung wir Euch nicht vorenthalten wollen! Wie immer dient diese Aufstellung weder der Denunzierung Einzelner noch der Belustigung der Allgemeinheit, sondern soll Euch einerseits beim Verstehen der von Euch gemachten Fehler helfen, und andererseits vor oft gemachten Fehlern bewahren.

Vergleichsbäume, Problemkomplexitäten und untere Schranken

"Die Tiefe des Baumes ist die worst-case Laufzeit!"

Das ist nur "ein Bischen richtig". Die Aussage muesste eher lauten: Die Tiefe des Vergleichsbaumes ist eine untere Schranke für die Problemkomplexität. (Damit ist sie natürlich auch eine untere Schranke für die Laufzeiten aller denkbaren und undenkbaren Algorithmen.) Aber die Aussage "...ist die worst-case-Laufzeit" ist definitiv falsch:

1.) Nur Algorithmen haben Laufzeiten, Probleme nicht! (Diese haben Komplexitäten.)

2.) Die Bezeichnung "worst-case" bezieht sich nur auf die Eingabe eines Algorithmus, und ersetzt daher nicht die Angabe, dass es sich nur um eine untere Schranke der Problemkomplexität handelt.

Es handelt sich deswegen nur um eine untere Schranke der Problemkomplexität, weil bei der Konstruktion des Vergleichsbaumes i.A. zahlreiche, vereinfachende Annahmen getroffen worden sind. Insbesondere wird i.A. der niedrigste aller denkbaren Vergleichsbäume, also der vollbesetzte Baum, betrachtet.

"Alle Werte kleiner als diese Komplexität sind eine untere Schranke, und können nicht erreicht werden!"

Richtig ist, dass wenn ein Wert eine untere Schranke ist, auch alle kleineren Werte untere Schranken sind.

Richtig ist weiterhin, dass der gesuchte Wert (also in unserem Fall die Problemkomplexität) jede untere Schranke für ihn definitionsgemäß niemals unterschreiten kann!

Aber falsch ist, dass untere Schranken a priori von dem gesuchten Wert nicht erreicht werden können: diese Aussage gilt nur dann, wenn noch "größere" untere Schranken vorhanden sind!

Dazu ein Beispiel: Allgemeine Sortierverfahren haben im worst-case immer eine Laufzeit von mindestens n log n (also OMEGA(n log n)). Anders ausgedrückt: Das Problem des allgemeinen Sortierens hat eine Komplexität von n log n. (Bei Aussagen über Problemkomplexitäten werden grundsätzlich nur worst-case-Laufzeiten betrachtet, es ist also nicht nötig, von einer "worst-case-Komplexität" zu sprechen.) Eine untere Schranke für die Komplexität dieses Problems ist also z.B. n log n. Aber auch n und log n und Wurzel(n) sind untere Schranken dafür! Hätten wir also z.B. nur log n als untere Schranke ermittelt, könnten wir keine Aussage darüber machen, ob man in log n allgemein sortieren kann - oder nicht. Erst durch eine "größere", also schärfere, untere Schranke wie z.B. n oder n log n können wir mit Sicherheit sagen, dass man nicht mit der Laufzeit log n sortieren kann.

Bei einem Beweis für ein untere Schranke einer Problemkomplexität darf man ruhig "vereinfachende" Annahmen treffen, die dazu führen, dass die untere Schranke, die man ermittelt, etwas niedriger (und damit: ungenauer! schlechter!) wird. Man darf aber unter gar keinen Umständen "verkomplizierende" Annahmen treffen, die zur Folge haben, dass man eine "untere Schranke" "beweist", die viel zu hoch ist, und demzufolge gar keine untere Schranke mehr sein muß!

Bezogen auf das Problem des allgemeinen Sortierens bedeutet das: Wenn man vereinfachende Annahmen trifft, und herausbekommt, dass eine untere Schranke für die Komplexität des allgemeinen Sortierproblems Wurzel(n) ist, dann ist diese Aussage immer noch richtig - allerdings ist sie relativ ungenau und unnütz geworden. Wenn man aber verkomplizierende Annahmen trifft, könnte man herausbekommen, dass eine untere Schranke für die Komplexität des allgemeinen Sortierproblems n^2 ist - und diese Aussage ist definitiv falsch, denn man könnte daraus schlussfolgern, dass man in n log n nicht allgemein sortieren kann, und auch niemals können wird! (Was man aber sehr wohl kann!)

Beweistechniken

"Da es nur eine Abschätzung ist, ignoriere ich Rundungen!"

Nein, bitte Rundungen nicht grundsätzlich und pauschal ignorieren! Zwar ist es so, dass sich Rundungen oftmals nicht oder nur minimal auf das Ergebnis auswirken, vor Allem dann, wenn man nur Größenordnungen betrachtet, aber dies muß nicht a priori so sein! Je nachdem, wo man rundet, kann es einem durchaus das Ergebnis zerstören!

Also wenn gerundet wird, dann entweder begründen, warum dies erlaubt ist, oder lieber überhaupt nichts dazu schreiben ;-)

"Mit Mergesort kann ich in O(n log n) sortieren, also kann ich für den Fall, dass d=n mit Mergesort in O(d log n) abstandsbeschränkt sortieren.

Man kann einen Beweis nicht dadurch erbringen, dass man die Voraussetzungen oder das zu Zeigende spezialisiert, und dann einen spezialisierten Beweis erbringt. "Beweis durch Spezialisierung" ist keine probate Beweistechnik!

Eine Laufzeitaussage der Form "O(d log n)" hat für jedes d und jedes n zu gelten - und auch so bewiesen zu werden. (Anderenfalls wäre eine solche Aussage eher sinnfrei.)

Allgemeine Sortierverfahren

"Man benutzt n mal die binäre Suche, und fügt die Element jeweils ein. Also hat man O(n)."

Prinzipiell richtig, aber nur dann, wenn man auch eine Datenstruktur vorstellt, die in O(1) sowohl einfügen als auch auslesen kann - denn das ist keine triviale Datenstruktur! (Ein Array und eine Liste können das jedenfalls nicht. In einer Liste kann man nicht auf jedes Element zugreifen, sondern muss sich "durchhangeln", also O(n). In einem Array geht das zwar in O(1), allerdings kann man dort nur in O(n) einfügen, da man erst alle Elemente rechts davon um eins verschieben muß! Naja, und n * O(n) ist eben kein O(n) mehr!)

"Quicksort hat eine Laufzeit von O(n log n)!"

Ja, aber nur im average-case (erwarteter Fall, mittlerer Fall) und im best-case (bester Fall. Im worst-case hat der Quicksort eine Laufzeit von O(n^2)! Allgemeine Sortierverfahren, die auch im worst-case eine Laufzeit von O(n log n) haben, sind z.B. Heapsort und Mergesort.

Sonstige Anmerkungen

"In einer Folge kann jedes Element an d Positionen stehen, also gibt es n^d Permutationen!"

Nein! Mit dieser Logik gäbe es ganz allgemein für eine Folge mit n Elementen n^n Permutationen - das ist falsch! Es gibt nämlich nur n! Permutationen. Der Grund dafür ist, dass z.B. bei einer Folge mit n Elementen das erste Element zwar durchaus n Möglichkeiten besitzt, an die es sich positionieren kann, aber z.B. das letzte Element nur noch eine einzige Möglichkeit besitzt - nämlich die einzige noch freie Position.

"Es gibt n Verkehrssünder und 15 Bundesländer!"

Gegenwärtig gibt es in der BR 16 Bundesländer, auch wenn hin und wieder das Gegenteil behauptet wird (siehe z.B. CSU Schweinfurt (Stand: 13.12.2001). Die 1996 von der SPD-Regierung beschlossene Fusion der Länder Berlin und Brandenburg ist am 5.5.1996 an einem Volksentscheid gescheitert. Demzufolge hat die BR auch weiterhin 16, und nicht 15 Bundesländer ;-)

Für die Korrektheit des Algorithmus ist diese Tatsache nicht von Belang ;-)

Klicke hier, um zurück zur Hauptseite zu gehen.