Theta-Notation bei konstanter Zeit. Warum verwenden wir die 1?

In asymptotischer Notation, wenn angegeben wird, dass die Lösung, wenn die Problemgröße klein genug ist (z. B. n<cfür eine Konstante c), eine konstante Zeit benötigt und als geschrieben wird Theta(1).
Warum schreiben wir 1 in die Theta?
Was bedeutet das 1? Warum nicht Theta(c)?

Diese Notationen sollen das asymptotische Wachstum bezeichnen. Konstanten wachsen nicht und daher ist es ziemlich gleich, welche Konstante Sie wählen. Es gibt jedoch eine Konvention, bei der Sie 1 auswählen, um kein Wachstum anzuzeigen.

Ich gehe davon aus, dass dies darauf zurückzuführen ist, dass Sie die fraglichen mathematischen Begriffe vereinfachen möchten. Wenn Sie einen konstanten Faktor haben, teilen Sie ihn einfach durch und alles, was davon übrig bleibt, ist 1. Dies erleichtert Vergleiche.

Beispiel:

O (34 * n ^ 2) = O (1 * n ^ 2) = O (n ^ 2)

und

O (2567.2343 * n ^ 2/5) = O (n ^ 2)

Verstehst du, was ich meine? Da diese mathematischen Begriffe immer komplizierter werden, möchten Sie keine verrauschten Konstanten haben, wenn sie für die Informationen, an denen Sie interessiert sind, nicht relevant sind. Warum sollte ich O (2342.4534675767) schreiben, wenn es mit O einfacher ausgedrückt werden kann? (1), der den Sachverhalt eindeutig mitteilt.

Darüber hinaus impliziert der Wikipedia-Artikel über Zeitkomplexität auch, dass es sich um eine Konvention handelt:

Ein Algorithmus wird als konstante Zeit bezeichnet (auch als O (1) -Zeit geschrieben) ...

Dies ist alles sehr handgewellt, aber es gibt einen mathematischen Grund, warum wir Theta (c) nicht verwenden und stattdessen Theta (1) verwenden. Ich werde stattdessen die Big O-Notation verwenden, um dies zu zeigen.

Dies hat mit einer Eigenschaft der Notation Big Theta (sowie Big O und Big Omega) zu tun. Wenn Sie eine Funktion mit Wachstumsrate haben O(g(x))und eine andere mit Wachstumsrate , O(c * g(x))wo ceine Konstante ist, würden Sie sagen , dass sie die gleiche Wachstumsrate haben. Das istO(c * g(x)) = O(g(x))

Wir können dies sagen, weil die Definition der Big O-Notation ( f(x) = O(g(x))) bedeutet, dass wir eine Funktion f(x)und Funktion haben, g(x)so dass |f(x)| <= k * |g(x)|für einige konstante kund ausreichend große Werte von x. Wenn cwir mit der Konstanten multiplizieren , hätten wir dann:

O(c * g(x)) => k * |c * g(x)| = k * |c| * |g(x)| <= k' * g(x) wo k' = k * |c|

Beachten Sie, dass |k' * g(x)| <= k'' g(x)für einige konstante k''und ausreichend große Werte von x, was bedeutet, k' * g(x)mit einer Geschwindigkeit von O(g(x))und daher wächstO(c * g(x)) = O(g(x))

Wenn g(x) = 1wir O(1)Wachstum haben, sagt uns O(c)Wachstum für einen Wert von cnichts, weil die Konstante bereits in der Definition der Big O-Notation berücksichtigt ist. VereinfachtO(c) = O(1)

Natürlich könnten Sie Theta (c) (oder O (c)) schreiben, aber warum unterscheidet sich das von Theta (n)? n ist nur eine Variable, die die Größe der Eingabe angibt. Sie könnten schreiben "Die Funktion ist Theta (c), wobei c eine Konstante ist". Der wichtige Nachtrag ist ... wobei c eine Konstante ist . Sie müssen explizit angeben, dass ein Bezeichner keine Variable ist.

Betrachten Sie die Graphentheorie, bei der die Grenzen eines Algorithmus häufig als Funktion von | V | beschrieben werden und | E | oder die Knoten- bzw. Kantenanzahl. Dann kann es ratsam sein, "Die Funktion ist Theta (| V | * | E | ^ 2)" anzugeben.

Theta (1) ist jedoch immer eine Konstante - unter der Annahme normaler mathematischer Praktiken.

Bei der Theta-Notation geht es um Wachstum als Funktion einer Variablen - typischerweise n. Wenn geklärt werden müsste, welche Variable beabsichtigt ist, wäre die Art, sie zu schreiben, Theta (n ^ 0). Von dort aus ist es ein einfacher Schritt, die Identität n ^ 0 = 1 (für n! = 0) anzuwenden.

O ( c ) bedeutet insbesondere, dass die zugehörige Klasse von Algorithmen linear mit c wächst , wobei c die Größe einer Eingabe in den Algorithmus oder eines Parameters in den Algorithmus ist . Es ist nicht dasselbe c , das zur Erklärung der O-Notation verwendet wird, da dieses c nur für die Erklärung relevant ist, nicht für die Verwendung. O ( c ) enthält ein anderes c , das aus dem Algorithmus-Eingabekontext stammen muss.