Algorithmen Obere und untere Schranken

Obere Schranken

Im Sommer­schluss­verkauf wird vielfach geworben mit Angaben wie

Preise bis zu 70% reduziert

Dies bedeutet streng genommen nicht viel. Die Angabe bedeutet lediglich, dass man sich darauf verlassen kann, dass garantiert kein Preis um mehr als 70% reduziert worden ist. Manche Preise sind vielleicht um 5% reduziert worden, manche vielleicht auch um 10%, aber mit Sicherheit ist kein Preis z.B. um 80% reduziert worden.

Der Wert 70% ist hier die Obergrenze oder obere Schranke für den Preis­nachlass: "bis zu" bedeutet "".

Das Miss­verständnis, dem wir gern erliegen, ist durchaus beabsichtigt: Wir gehen davon aus, dass die obere Schranke auch angenommen wird, d.h. dass es tatsächlich Preise gibt, die um 70% reduziert worden sind.

Sehr beliebt und werblich sicher erfolgreich ist die Ankündigung

Preis­nachlass bis zu 70% und mehr

Hier ist die Aussage, dass der Preis­nachlass garantiert 70% ist, in einigen Fällen sogar 80%. Beides trifft z.B. für einen Preis­nachlass von 10% zu. Sowohl 70% als auch 80% sind obere Schranken für den Preis­nachlass.

 

Bei einem Algorithmus bedeutet die Angabe

Zeit­komplexität O(n²)

nicht, dass der Algorithmus quadratische Zeit­komplexität hat. Die Angabe bedeutet nur, dass der Algorithmus höchstens quadratische Zeit­komplexität hat. Er könnte tatsächlich z.B. lineare Zeit­komplexität haben, also eine Zeit­komplexität von O(n). Damit hat er automatisch eine Zeit­komplexität von O(n²), denn es gilt O(n)  O(n²)

Die Angabe O(n²) ist eine obere Schranke für die Zeit­komplexität des Algorithmus. Dies wird durch das Symbol O ausgedrückt. Häufig genügt uns die Angabe einer oberen Schranke; wir sind zufrieden, wenn der Algorithmus höchstens quadratische Zeit­komplexität hat – ist er schneller, umso besser.

Untere Schranken

Ebenfalls in der Werbung findet man Preisangaben wie

T-Shirts ab 9,95

Diese Angabe bedeutet, dass von den angebotenen T-Shirts garantiert keines weniger als 9,95 kostet. Die meisten kosten 14,95, manche sogar 19,95. Die Angabe 9,95 ist lediglich eine untere Schranke für den Preis: "ab" bedeutet "". Als Kunden gehen wir natürlich davon aus, dass die untere Schranke auch angenommen wird, d.h. dass es tatsächlich T-Shirts zu 9,95 gibt.

 

Die Tatsache, dass ein Algorithmus z.B. mindestens quadratische Zeit­komplexität hat, wird durch das Zeichen Ω ausgedrückt

Zeit­komplexität Ω(n²)

Der Algorithmus kann tatsächlich quadratische Zeit­komplexität haben, möglicher­weise aber auch kubische Zeit­komplexität oder sogar exponentielle Zeit­komplexität.

Θ

Wie aber drückt man es aus, dass ein Algorithmus tatsächlich quadratische Zeit­komplexität hat? Hierzu dient das Zeichen Θ (Theta). Es gilt

Θ(n²)  =  Ω(n²)    O(n²)

Ein Algorithmus, der sowohl mindestens quadratische Zeit­komplexität hat als auch höchstens quadratische Zeit­komplexität, hat tatsächlich genau quadratische Zeit­komplexität. Er hat dann eine Zeit­komplexität von Θ(n²).

Verwechslungsgefahr

Obere und untere Schranken sind leicht zu verwechseln, deshalb ist hier besondere Genauigkeit geboten. Eine Aussage wie

der Algorithmus hat eine Zeit­komplexität von mindestens O(n)

ist unsinnig, denn sie bedeutet, dass der Algorithmus mindestens höchstens c·n Schritte benötigt.

Entweder soll gesagt werden, dass der Algorithmus mindestens c·n Schritte benötigt, dann ist Ω(n) die richtige Angabe, oder höchstens c·n Schritte, dann ist O(n) die richtige Angabe, oder mindestens c₁·n Schritte und höchstens c₂·n Schritte, dann ist Θ(n) die richtige Angabe.

 

Zum Schluss folgt noch ein Beispiel dafür, wie schwierig der Umgang mit "mindestens", "höchstens", "ab", "bis zu" und "bis zu ... und mehr" ist.

Der Hersteller garantiert uns hier, dass der Dichtungs­streifen spätestens nach 8 Jahren undicht wird, vielleicht auch schon früher. Reklamationen sind zwecklos: Wird der Dichtungs­streifen nach einem halben Jahr undicht, kann der Hersteller sagen: "Stand ja drauf, Haltbarkeit weniger als 8 Jahre!". Dafür kann man aber vom Hersteller Ersatz verlangen, wenn der Dichtungs­streifen nach 9 Jahren immer noch dicht ist ... ¹)

Aufgaben

---

¹)  Mittlerweile ist das Zeichen auf der Packung entfernt worden. Die Haltbarkeit beträgt jetzt genau 8 Jahre.

 

Weiter mit:   [Asymptotische Komplexität]   oder

 

H.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   Datenschutz   ©   Created: 15.07.2008   Updated: 04.06.2018