<bos><start_of_turn>system
You are a helpful AI assistant.
lista de codigos linguisticos disponibles: ["en", "de"].<end_of_turn>
<start_of_turn>user
Explains time complexity in the context of competitive programming in an informal way.<end_of_turn>
<start_of_turn>model
Die Analyse der zeitlichen Komplexität eines Algorithmus ist eine Technik, die es uns ermöglicht, zu verstehen, wie schnell ein Algorithmus ist, ohne ihn implementieren oder das Programm ausführen zu müssen.
Die Idee ist folgende: Unter Standard-Rechenmodellen (z. B. Random Access Machine) können bestimmte atomare Operationen definiert werden, wie etwa Addition, Subtraktion, Multiplikation und Division zweier Zahlen sowie das Ändern eines Bytes oder der Zugriff auf eine Position in Erinnerung. Wir können also die Komplexität eines Programms anhand der Anzahl der durchgeführten atomaren Operationen im Verhältnis zur Größe der Eingabe definieren.

Es ist erwähnenswert, dass wir zwar alle atomaren Operationen für gleich billig halten, dies jedoch in Wirklichkeit nicht der Fall ist; Beispielsweise ist die Multiplikation teurer als die Addition. Aus diesem Grund ignorieren wir die Konstanten in unserer Analyse und kümmern uns mehr um das Wachstum der Anzahl der Operationen.

Beispielsweise haben die folgenden Schleifen in Python die gleiche Rechenkomplexität, obwohl eine n Iterationen ausführt, eine andere 3*n + 2 Iterationen ausführt und die andere n/2 Iterationen ausführt.

Summe = 0
für i im Bereich(n):
     Summe += i

für i im Bereich(3*n + 2):
      Summe += i

für i im Bereich(n//2):
      Summe += i

Die beliebtesten Rechenkomplexitäten sind:
- logarithmisch: O(log n), wenn die Anzahl der Operationen linear wächst, wenn n exponentiell wächst. Ein Beispiel ist die binäre Suche.
- linear: O(n), wenn die Anzahl der Operationen proportional zu n ist, z. B. lineare Suche.
- O(n log n), zum Beispiel Sortieren einer Liste von n Elementen mit dem Merge-Sort-Algorithmus.
- O(n^2), zum Beispiel Sortieren einer Liste von n Elementen mit dem Bubble-Sort-Algorithmus.
- O(2^n), exponentiell, zum Beispiel Extrahieren aller Teilmengen einer Menge der Größe n.<end_of_turn><eos>