Die O-Notation beschreibt das schlechteste Szenario der Laufzeit eines Algorithmus
Sie gibt an, wie die Laufzeit eines Algorithmus im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Wenn ein Algorithmus eine Laufzeit von O(n²) hat, bedeutet das, dass die Laufzeit im schlimmsten Fall quadratisch zur Eingabegröße n wächst.
Small-o-Notation (small o)
Die Small-o-Notation beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch kleiner ist als eine bestimmte Funktion.
Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus schneller wächst als eine bestimmte Funktion, aber langsamer als eine andere.
Wenn ein Algorithmus eine Laufzeit von o(n²) hat, bedeutet das, dass die Laufzeit asymptotisch kleiner ist als n², aber nicht notwendigerweise im schlimmsten Fall.
Omega-Notation (Big Ω)
Die Omega-Notation beschreibt das beste Szenarioder Laufzeit eines Algorithmus.
Sie gibt an, wie die Laufzeit eines Algorithmus im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Wenn ein Algorithmus eine Laufzeit von Ω(n) hat, bedeutet das, dass die Laufzeit im besten Fall linear zur Eingabegröße n wächst.
Kleine Omega-Notation (kleines ω)
Die kleine Omega-Notation beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch größer ist als eine bestimmte Funktion.
Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus langsamer wächst als eine bestimmte Funktion, aber schneller als eine andere.
Wenn ein Algorithmus eine Laufzeit von ω(n) hat, bedeutet das, dass die Laufzeit asymptotisch größer ist als n, aber nicht notwendigerweise im besten Fall.
Theta-Notation (Θ)
Die Theta-Notation beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch zwischen zwei Funktionen liegt.
Sie wird verwendet, um die genaue Wachstumsrate der Laufzeit eines Algorithmus zu beschreiben, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt.
Wenn ein Algorithmus eine Laufzeit von Θ(n²) hat, bedeutet das, dass die Laufzeit asymptotisch sowohl durch n² nach oben als auch nach unten beschränkt ist.
Exakte Wachstumsrate (sowohl obere als auch untere Schranke)
Notationen (tabellarisch)
O-Notation (Big O)
Zweck: Beschreibt das schlechteste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Omega-Notation (Big Ω)
Zweck: Beschreibt das beste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht.
Small-o-Notation (kleines o)
Zweck: Beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch kleiner ist als eine bestimmte Funktion.
Theta-Notation (Θ)
Zweck: Beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt die genaue Wachstumsrate der Laufzeit an, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt.
Kleine Omega-Notation (kleines ω)
Zweck: Beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch größer ist als eine bestimmte Funktion.
Dieser Algorithmus ist eine Erweiterung des normalen Bubble Sort Algorithmus. Wie dieser wird hierbei ein Array durchlaufen und das Element der aktuellen Iteration mit dem Nachfolgeelement getauscht, wenn dieses kleiner ist. Dadurch blubbern die Zahlen vom Array-Anfang bis zum Ende in einen sortierten Bereich auf der rechten Seite des Arrays nach oben.
Der optimierte Bubble Sort-Algorithmus bricht weitere Iterationen ab, wenn er in in seiner if-Bedingung nichts mehr zum Tauschen gefunden hat. Dies vermerkt er in einer bool-Variable, was die umgebende do…while-Schleife nutzt um den Algorithmus abzubrechen.
package AlgoDat;
public class OptimizedBubbleSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static OptimizedBubbleSort program;
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Konstruktor
public OptimizedBubbleSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
// Da wir eine do .. while-Schleife nun nutzen,
// zählen wir einen Index darin runter um diesen
// im Array jederzeit adressieren zu können.
int sortierterBereichRechts = myArray.length;
// Wenn in einer Iteration nix getauscht wurde
// wird das für alle weiteren auch der Fall sein.
// In dem Fall kann der Algorithmus enden.
boolean hatteNochWasZuTun = false;
do
{
// Am Anfang gibts nix zu tun
hatteNochWasZuTun = false;
System.out.println("Iteration: " + (myArray.length - sortierterBereichRechts + 1));
for (int i = 0; i < sortierterBereichRechts - 1; i++)
{
if (myArray[i] > myArray[i + 1])
{
this.vertausche(myArray, i, i + 1);
System.out.print("Tausche: ");
this.OutputOfIntArray(myArray);
hatteNochWasZuTun = true;
}
}
// Der sortierte Bereich wächst
sortierterBereichRechts--;
}
while (hatteNochWasZuTun);
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
}
public void vertausche(int[] arrayToSwap, int idx1, int idx2)
{
int swapVar = arrayToSwap[idx1];
arrayToSwap[idx1] = arrayToSwap[idx2];
arrayToSwap[idx2] = swapVar;
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new OptimizedBubbleSort();
}
}
Der QuickSort-Algorithmus ist ein rekursiver Sortieralgorithmus nach dem Teile- und Herrsche-Prinzip. Er ruft sich so lange selber auf, bis alle Array-Elemente auf der linken und rechten Stack-Seite eines Pivot-Elements sortiert sind. Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Anschließend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekusion.
Der Prinzip:
Auswahl eine zufälligen Pivot-Elements (muss nicht das kleinste Element im Array sein)
Sortierung aller kleineren Zahlen als das Pivot-Element auf die linke Seite des Stapels/Stacks
Sortierung aller größeren Zahlen als das Pivot-Element auf die rechte Seite des Stapels/Stacks
Rekursiver Aufruf für die linke Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine kleinere Zahl mehr gefunden wurde, die links vom Pivot-Element einsortiert werden kann.
Rekursiver Aufruf für die rechte Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine größere Zahl mehr gefunden wurde, die rechts vom Pivot-Element einsortiert werden kann.
package AlgoDat;
public class QuickSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static QuickSort program;
private java.util.Random rnd = new java.util.Random();
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Generiert ein zufälliges Integer-Array der Größe size mit Werten zwischen 0 und upperLimit
public int[] generateIntegerArrayOfSize(int size, int upperLimit)
{
int[] generatedArray = new int[size];
for (int i = 0; i < generatedArray.length; i++)
{
generatedArray[i] = rnd.nextInt(upperLimit);
}
return generatedArray;
}
public void makeQuickSort(int[] arrayToSort, int fromIndex, int toIndex)
{
// Rekursionsabbruch
if (fromIndex >= toIndex)
{
return;
}
// Das Pivot-Element muss beim Teile-Herrsche-Prinzip nicht die kleinste Zahl im Array sein
// und kann willkürlich gewählt werden - wie hier das letzte Element des Array
int pivot = arrayToSort[toIndex];
// Im Average Case performt der Quicksort aber besser, wenn es zufällig ausgewählt wird
// int pivotIndex = rnd.nextInt(toIndex - fromIndex) + fromIndex;
// int pivot = arrayToSort[pivotIndex];
// Diese Pointer beinhalten den Index der Elemente, die miteinander verglichen und ggfs. vertauscht werden, wenn sie kleiner/größer als das Pivot sind.
int leftPointer = fromIndex;
int rightPointer = toIndex;
// Partitioniere, so lange wie sich die Pointer nicht in die Quere kommen
while (leftPointer < rightPointer)
{
// Verschiebe leftPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
// (oder wie sich die Pointer nicht überschneiden)
while (arrayToSort[leftPointer] <= pivot && leftPointer < rightPointer)
{
leftPointer++;
}
// Verschiebe rightPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
// (oder wie sich die Pointer nicht überschneiden)
while (arrayToSort[rightPointer] >= pivot && leftPointer < rightPointer)
{
rightPointer--;
}
// Vertausche die Elemente am Index von leftPointer und rightPointer
int swapVar = arrayToSort[leftPointer];
arrayToSort[leftPointer] = arrayToSort[rightPointer];
arrayToSort[rightPointer] = swapVar;
}
// Vertausche die Elemente am Array-Index von leftPointer und toIndex
int swapVar = arrayToSort[leftPointer];
arrayToSort[leftPointer] = arrayToSort[toIndex];
arrayToSort[toIndex] = swapVar;
// QuickSort für die linke Seite vom Pivot-Element
this.makeQuickSort(arrayToSort, fromIndex, leftPointer - 1);
// QuickSort für die rechte Seite vom Pivot-Element
this.makeQuickSort(arrayToSort, leftPointer + 1, toIndex);
}
// Konstruktor
public QuickSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
long startZeit = System.nanoTime();
// this.OutputOfIntArray(this.generateIntegerArrayOfSize(1000, 100));
this.makeQuickSort(myArray, 0, myArray.length - 1);
long endZeit = System.nanoTime();
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
System.out.println("Ich habe " + (endZeit - startZeit) + " ns gebraucht.");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new QuickSort();
}
}
Ausgabe
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Ich habe 7200 ns gebraucht.
Komplexität: O-Notation (Ordnung)
Der Quick-Sort hat im Average-Case die Komplexität O(n* log(n)) und im Worst-Case die Komplexität O(n²).
Die binäre Suche funktioniert nur auf einem bereits sortiertem Datenbestand, daher wird die Zeit für das Sortieren des Arrays „myArray“ mit Merge-Sort auf die Such-Zeit addiert. Da die 11 Elemente im Beispiel-Array sehr wenige sind, sind die Zeiten in ms wenig repräsentativ.
package AlgoDat;
public class SearchAlgorithm {
// Zu durchsuchendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static SearchAlgorithm program;
public int linearSearch(int[] array, int contentToSearchFor)
{
for (int i = 0; i < array.length; i++)
{
if (array[i] == contentToSearchFor)
{
return i;
}
}
return -1;
}
public int binarySearch(int[] myArray, int contentToSearchFor)
{
// Start conditions
int lowIndex = 0;
int highIndex = myArray.length - 1;
while (lowIndex <= highIndex)
{
int middlePosition = (lowIndex + highIndex) / 2;
int middleContent = myArray[middlePosition];
if (contentToSearchFor == middleContent)
{
return middlePosition;
}
// Halbieren der Suchelemente
if (contentToSearchFor < middleContent)
{
highIndex = middlePosition - 1;
}
else
{
lowIndex = middlePosition + 1;
}
}
// Außerhalb der While-Schleife wissen wir, dass wir
// das Element nicht gefunden haben :-(
return -1;
}
// Konstruktor
public SearchAlgorithm()
{
int arrayContent = -1;
long startTime = 0;
long endTime = 0;
int index = -1;
long passedTime = 0;
System.out.println("Lineare Suche");
System.out.println("=============");
// Not found
arrayContent = 23;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche not found: " + passedTime + " ms.");
// Best case
arrayContent = 22;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Best-Case: " + passedTime + " ms.");
// Average case
arrayContent = 3;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Average-Case: " + passedTime + " ms.");
// Worst case
arrayContent = 1;
startTime = System.nanoTime();
index = linearSearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = endTime - startTime;
System.out.println("Lineare Suche Worst-Case: " + passedTime + " ms.");
System.out.println("Binäre Suche");
System.out.println("============");
/*********************************************/
/* die binäre Suche benötigt ein sortiertes */
/* Array, damit sie funktioniert. */
/*********************************************/
startTime = System.nanoTime();
this.mergeSort(myArray);
endTime = System.nanoTime();
long passedSortTime = endTime - startTime;
// Not found
arrayContent = 23;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche not found: " + passedTime + " ms.");
// Best case
arrayContent = 22;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche erstes Element: " + passedTime + " ms.");
// Average case
arrayContent = 3;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche mittleres Element: " + passedTime + " ms.");
// Worst case
arrayContent = 1;
startTime = System.nanoTime();
index = binarySearch(myArray, arrayContent);
System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
endTime = System.nanoTime();
passedTime = passedSortTime + (endTime - startTime);
System.out.println("Binäre Suche letztes Element: " + passedTime + " ms.");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new SearchAlgorithm();
}
/**************/
/* MERGE SORT */
/**************/
public void mergeSort(int myArray[])
{
// Abbruchbedingung der Rekursion im Sinne von Teile-und-Herrsche-Algorithmen
if (myArray.length == 1) return;
// weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
int indexHaelfte = myArray.length / 2;
int[] linkeHaelfte = new int[indexHaelfte];
// Die abgerundete Ganzzahl kann von der Länge abgezogen werden
// um die Größe des rechten Arrays zu erhalten.
int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
// Befülle die linke Hälfte
for (int i = 0; i < indexHaelfte; i++)
{
linkeHaelfte[i] = myArray[i];
}
// Befülle die rechte Hälfte
for (int i = indexHaelfte; i < myArray.length; i++)
{
rechteHaelfte[i - indexHaelfte] = myArray[i];
}
// Hier ist der rekursive Aufruf, indem die beiden Hälften an
// die mergeSort-Methode selbst übergeben wird.
this.mergeSort(linkeHaelfte);
this.mergeSort(rechteHaelfte);
// Hier werden die beiden Arrays wieder kombiniert (geMerged)
this.merge(myArray, linkeHaelfte, rechteHaelfte);
}
private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
{
int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
// Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
// in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
{
if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
}
else
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
}
iteratorMergeArray++;
}
// Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorLinks < linkeHaelfte.length)
{
mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
iteratorLinks++;
iteratorMergeArray++;
}
// Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
// werden diese dem Merged Array hinzugefügt
while (iteratorRechts < rechteHaelfte.length)
{
mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
iteratorRechts++;
iteratorMergeArray++;
}
}
}
Ausgabe
Lineare Suche
=============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Lineare Suche not found: 20969800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 0 von myArray[]. Lineare Suche Best-Case: 9613200 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 5 von myArray[]. Lineare Suche Average-Case: 337400 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 10 von myArray[]. Lineare Suche Worst-Case: 270200 ms.
Binäre Suche
============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Binäre Suche not found: 206800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 10 von myArray[]. Binäre Suche erstes Element: 271400 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 2 von myArray[]. Binäre Suche mittleres Element: 306700 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 0 von myArray[]. Binäre Suche letztes Element: 302800 ms.
Komplexität: O-Notation (Ordnung)
Die Komplexität der binären Suche wird mit
beschrieben, wobei die Komplexität des vorangegangenen Merge-Sort-Algorithmus mitgerechnet werden muss, da die binäre Suche nur auf einem binären Datenbestand funktioniert. Somit ergibt sich
, wobei die additiven Bestandteile log(n) wegfallen. Somit ergibt sich im vorliegenden Falle die Komplexität O(n*log(n)) wegen der vorangegangen Sortierung. Ist diese nicht notwendig bleibt es bei der O-Notation O(log(n)).
Bei der rekursiven Fakultät handelt es sich um einen rekursiven Funktionsaufruf:
package AlgoDat;
public class RekursiveFakultaet {
// Zu sortierendes Array
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static RekursiveFakultaet program;
public long berechneFakultaet(int teilFakultaet)
{
// Abbruchbedingung der Rekursion wenn 1 erreicht ist
if (teilFakultaet == 1) return 1;
// Multipliziere rekursiv f(n) = n * f(n - 1) bis 1
return teilFakultaet * berechneFakultaet(teilFakultaet - 1);
}
// Konstruktor
public RekursiveFakultaet()
{
System.out.println(this.berechneFakultaet(25) + "");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new RekursiveFakultaet();
}
}
Ausgabe
7034535277573963776
Komplexität: O-Notation (Ordnung)
Der rekursive Aufruf dieser Art kann als primitiv rekursiven Klasse gezählt werden und besitzt die lineare Komplexität / O-Notation:
