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

9

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)?

user10326
quelle

Antworten:

8

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) ...

Falke
quelle
Ich verstehe. Aber warum nicht einfach Theta (c), um eine Konstante abzudecken? Es ist nur eine Konvention?
user10326
8
@ user10326: Ich denke, weil "c" falsch interpretiert werden könnte, muss man eindeutig angeben, dass es eine Konstante ist, während "1" den gleichen Job eindeutig erledigt.
Falcon
Die tatsächliche Anzahl ist also irrelevant. Wir verwenden 1 anstelle von 5 als Konvention.
user10326
1
@ user10326: Ja, weil es keinen Unterschied macht. Aber ich würde auf "0" verzichten, da dies zu großer Verwirrung führen könnte.
Falcon
@ user10326: Falcon seine Antwort machte vollkommen Sinn, nicht wahr? Wenn es 5 statt 1 wäre, O(5 * n^2)würde sich das Fallenlassen von 5 weniger natürlich anfühlen, während das Fallenlassen * 1eine grundlegende Mathematik ist.
Steven Jeuris
13

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)

Jay Lindquist
quelle
3

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.

Max
quelle
Theta(1) however is always a constantDies ist der Teil, den ich nicht bekomme. Theta (c) ist immer auch eine Konstante. Richtig? Also habe ich mich gefragt, ob das 1eine besondere Bedeutung hat
user10326
5
@ user10326: nein, cist nicht immer eine Konstante, da ces sich um eine Variable handelt, wenn Sie nicht explizit angeben, dass sie tatsächlich als Konstante interpretiert werden soll ... Dies ist genau der subtile Unterschied, der durch vermieden wird 1.
Blubb
Ok, aber es repräsentiert eine konstante Zeit.
user10326
2
@ user10326: Nein, nein, es handelt sich nicht um eine konstante Zeit. Es repräsentiert die Zeit, die linear mit c wächst. Diese sind unterschiedlich , da Sie etwas Zusätzliches benötigen, um zu erzwingen, dass sich der Wert von c niemals ändert, während sich 1 niemals ändert.
jprete
1
@ user10326: Oder einfacher gesagt: cist keine Konstante; cist ein Brief. Andere Buchstaben stellen Variablen dar. Wie soll der Leser wissen, dass dies nicht so gut ist?
Random832
0

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.

Peter Taylor
quelle
Aber warum sagen Sie n^0, um konstante Zeit zu bezeichnen und nicht n^1in Ihrem Beispiel?
user10326
@ user10326, da n ^ 1 = n nicht konstant ist. Es wächst linear.
Peter Taylor
0

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.

jprete
quelle