Big-O-Notation

In den nächsten Wochen möchte ich einige Beiträge zum Thema „Algorithmen“ veröffentlichen. Den Auftakt zu dieser Artikelserie macht eine Übersicht zur Big-O-Notation.

Was ist die Big-O-Notation?

Bei der Entwicklung bzw. der Auswahl eines Algorithmus kommt es auf die Frage an, wie schnell dieser ist. Hinsichtlich der Geschwindigkeit, wie auch der Größe des verwendeten Speichers, wird als Indikator die Big-O-Notation verwendet. Nachfolgende Tabelle gibt eine Auskunft über die Big-O-Werte:

Big-O Bezeichnung Beschreibung
O(1) konstant Dies ist der best mögliche Wert. Es bedeutet, dass der Algorithmus stets die gleiche Zeit benötigt, unabhängig davon, wie viele Daten verarbeitet werden müssen.
O(log n) logarithmisch Dies ist ein ziemlich guter Wert. Diese Art von Algorithmen halbieren die vorhanden Daten bei jedem Durchlauf (Beispiel: Binär-Suche). Selbst bei einer großen Datenmenge ist ein solcher Algorithmus sehr schnell.
O(n) linear Auch dieser Algorithmus hat eine gute Performance. Eine Verdopplung der vorhanden Daten führt zu eine Verdoppelung der benötigten Zeit (Beispiel: Sequentielle Suche)
O(n log n) loglinear Dies ist ein noch annehmbarer Wert, wenn auch nicht so gut wie bei der linearen Big-O-Notation.
O(n2) quadratisch Von nun an geht es “den Bach runter”. Dieser Algorithmus ist langsam. Eine Verdoppelung der vorhandenen Daten führt zu einer Vervierfachung der aufzuwendenden Zeit. (Beispiel: Algorithmen, die verschachtelte Schleifen verwenden.)
O(n3) kubisch Dies ist eine schlechte Performance. Eine Verdoppelung der Daten führt zu einer Verachtfachung der Zeit.
O(2n) exponentiell Und es wird nicht besser. Diese Algorithmen sollte man eher vermeiden. Nur das Hinzufügen eines Bits verdoppelt die aufzuwendende Zeit.

 

Nachfolgende Abbildung verdeutlicht die Big-O-Werte grafisch.

big-o-notation

Als Faustformel für die Praxis kann man sich merken, dass ein Algorithmus, der über alle n-Elemente einer Eingabe in einer Schleife iteriert, den Wert O(n) hat. Bei zwei verschachtelten Schleifen ist man beim Wert O(n2), bei drei verschachtelten Schleifen bei O(n3), usw.

Man sollte aber bedenken, dass die Orientierung anhand der Big-O-Notation nur bei einer sehr hohen Anzahl von n-Elementen aussagekräftig ist.

Im nächsten Artikel geht es dann um den ersten Suchalgorithmus, die lineare Suche in Swift und Python.

Anmerkung: Die Grafik wurde übrigens mit Python3.6/Matplotlib erstellt. Den Code dafür könnt Ihr Euch bei Github ansehen.

Durch Benutzung dieser Website erklären Sie sich mit der Verwendung von Cookies einverstanden. Mehr Informationen

Die Verwendung von Cookies dient dazu, Inhalte und Anzeigen zu personalisieren, Funktionen für soziale Medien anbieten zu können und die Zugriffe auf diese Website zu analysieren. Außerdem werden Informationen zur Nutzung dieser Webseite an Partner für soziale Medien, Werbung und Analysen weitergegeben.

Schließen