Summen von Landau Bedingungen überarbeitet

Ich fragte eine (Samen) Frage zu Summen von Landau Bedingungen vor , zu versuchen , die Gefahren zu beurteilen , der Asymptotiken Notation in arithmetics, mit gemischtem Erfolg zu missbrauchen.

Nun hier unsere Wiederholung Guru JEFFE tut im Wesentlichen diese:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

Obwohl das Endergebnis korrekt ist, denke ich, dass dies falsch ist. Warum? Wenn wir die gesamte Existenz impliziter Konstanten hinzufügen (nur die Obergrenze), haben wir

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$ .

Wie berechnen wir nun aus ? Die Antwort ist, glaube ich, dass wir nicht können: muss für alle gebunden sein, aber wir bekommen mehr wenn wächst. Wir wissen nichts über sie; kann sehr gut von abhängen , daher können wir keine Grenze annehmen: Ein endliches existiert möglicherweise nicht. $c$ $c_1, \dots, c_n$ $c$ $n$ $c_i$ $n$ $c_i$ $i$ $c$

Darüber hinaus gibt es diese subtile Frage, welche Variable auf der linken Seite ins Unendliche geht - oder ? Beide? Wenn (aus Gründen der Kompatibilität), was bedeutet , wenn man weiß, dass ? Bedeutet das nicht nur ? Wenn ja, können wir die Summe nicht besser als binden . $i$ $n$ $n$ $\Theta(1/i)$ $1 \leq i \leq n$ $\Theta(1)$ $\Theta(n)$

Wo bleibt uns das? Ist es ein offensichtlicher Fehler? Eine subtile? Oder ist es nur der üblicher Missbrauch der Notation und wir sollen nicht sehen aus dem Zusammenhang gerissen Zeichen wie diese? Können wir eine (streng) korrekte Regel formulieren, um (bestimmte) Summen von Landau-Begriffen zu bewerten? $=$

Ich denke , dass die wichtigste Frage ist: Was ist ? Wenn wir es konstant (wie es ist innerhalb des Umfangs der Summe) wir counterexamples leicht aufbauen können. Wenn es nicht konstant ist, habe ich keine Ahnung, wie ich es lesen soll. $i$

terminology asymptotics landau-notation Raphael
quelle

Diese Frage zu math.SE ist eine gute Lektüre über Arithmetik mit Landau-Begriffen im Allgemeinen.

Raphael

Aus dem von Ihnen angegebenen Link geht hervor, dass die Gleichheit entweder eine Teilmengenrelation oder eine "Ist in" -Relation (dh ) ist. Für sagen Sie nur, dass es oben und unten durch eine Konstante begrenzt ist. Warum nicht und wählen ?

\in

$\in$

Θ

$\Theta$

c = min (c_{1}, c_{2}, \dots, c_{n})

$c = \min(c_1, c_2, \cdots, c_n)$

C = max (c_{1}, c_{2}, \dots, c_{n})

$C = \max(c_1, c_2, \cdots, c_n)$

user834

Warte, Bucky. Ich habe keine Zusammenfassung mit einem Theta geschrieben. Ich habe eine Wiederholung mit einem Theta geschrieben. Interpretieren Sie die Wiederholung " " wirklich als etwas anderes als "Es gibt eine Funktion so dass "?

t (n) = Θ (1 / n) + t (n - 1)

$t(n) = \Theta(1/n) + t(n-1)$

f \in Θ_{x \to \infty} (x \mapsto 1 / x)

$f \in \Theta_{x\to \infty}(x\mapsto 1/x)$

t (n) = f (n) + t (n - 1)

$t(n) = f(n) + t(n-1)$

JeffE

@ Raphael Nein, die Wiederholung ist mathematisch nicht die gleiche wie die Summe, genau aus dem Grund, den Sie beschreiben! Die Wiederholung enthält genau einen Theta-Term, der sich eindeutig auf eine einzelne Funktion bezieht.

JeffE

Das ist nicht sehr intuitiv - ich stimme überhaupt nicht zu, aber ich denke, es ist eine Frage des Geschmacks und der Erfahrung.

JeffE

Antworten:

Sieht für mich in der folgenden Konvention richtig aus:

$S_n = \sum_{k=1}^{n} \Theta(1/k)$ ist eine bequeme Notation für

Es gibt ein (als ), so dass $f(x) \in \Theta(1/x)$ $x \to \infty$

$S_n = \sum_{k=1}^{n} f(k)$ .

Somit sind die (oder mit der Notation in dieser Antwort ), die Sie erhalten, nicht wirklich von abhängig . $c_i$ $c_k$ $k$

Nach dieser Interpretation ist es tatsächlich wahr, dass . $S_n = \Theta(H_n)$

Tatsächlich zeigt er in Jeffs Antwort, dass wobei , so dass es mit der obigen Interpretation übereinstimmt. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

Die Verwirrung scheint sich aus dem mentalen "Abrollen" der und der Annahme unterschiedlicher Funktionen für jedes Auftreten von ... $\sum$ $\Theta$

Aryabhata
quelle

Jup, aber jedes kann seine eigene Funktion und Konstante haben. Diese Konvention funktioniert also nur mit dem Kontext, wenn wir wissen, dass die Landau-Begriffe aus einer etwas "einheitlichen" (in und ) Definition der Summanden stammen.

Θ

$\Theta$

k

$k$

n

$n$

Raphael

@Raphael: Es scheint sinnlos, sich abzuwickeln und dann verschiedene zuzulassen : Die Konstanten hängen dann von der Variablen ab! und es wird eine falsche Verwendung von , vorausgesetzt, die Variable ist (oder in der obigen Antwort). Selbst wenn wir annehmen, dass die Variable ist, sieht sie für mich immer noch bedeutungslos aus.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Aryabhata

Im Prinzip jeder kann seine eigenen konstant, aber im besonderen Kontext Sie beschreiben , ist es klar , dass jeder ist nicht seine eigene Konstante hat.

Θ

$\Theta$

Θ

$\Theta$

JeffE

@ JeffE: Richtig. Wir können mehrere mit ihren eigenen Konstanten haben, solange die Konstanten wirklich konstant sind :-)

Θ

$\Theta$

Aryabhata

@JeffE Warum schreibst du nicht einfach, was du meinst, sondern bevorzugst etwas mehrdeutiges / falsches? Beachten Sie, dass meine aktualisierte Antwort jetzt einen Weg vorschlägt, dies zu tun. Ich würde mich über Kommentare dazu freuen. Abstimmungen ohne Grund helfen mir nicht zu verstehen, warum Leute meinen Standpunkt ablehnen.

Raphael

Ich glaube, ich habe das Problem gelöst. Im Wesentlichen: Durch die Verwendung von Landau-Begriffen wird die Variable der Summandenfunktion von der laufenden Variablen der Summe entkoppelt. Wir lesen sie immer noch als identisch, daher die Verwirrung.

Um es formal zu entwickeln, was macht

$\qquad \displaystyle S_n \in \sum_{i=1}^n \Theta(f(i)) \qquad \qquad\qquad (1)$

wirklich gemein? Nun gehe ich davon aus, dass diese lassen - nicht - bis ins Unendliche; Wenn wir , ergibt jede solche Summe (wenn die Summanden unabhängig von und daher konstant sind), was eindeutig falsch ist. Hier ist ein erstes Werbegeschenk, das wir für grobe Dinge machen: bin innerhalb der Summe gebunden (und konstant), aber wir lassen sie trotzdem bis ins Unendliche gehen? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

Wenn wir (für die Obergrenze funktioniert die Untergrenze ähnlich), erhalten wir $(1)$

$\qquad \displaystyle \exists f_1, \dots, f_n \in \Theta(f).\ S_n \leq \sum_{i=1}^n f_i(i)$

Jetzt ist klar, dass die Summe und der Parameter entkoppelt sind: Wir können das leicht so definieren , dass sie als Konstante verwenden. Im Beispiel aus der Frage können wir und haben $i$ $i$ $f_i$ $i$ $f_i(j) = i \cdot \frac{1}{j} \in \Theta(1/j)$

$\qquad \displaystyle \sum_{i=0}^n f_i(i) "=" \sum_{i=0}^n \Theta(1/j) = \sum_{i=0}^n \Theta(1/i)$

aber die ursprüngliche Summe ergibt eindeutig nichts in . Das Austauschen von gegen - was nur eine Umbenennung ist - im mag sich seltsam anfühlen, weil nicht unabhängig von resp. die Summe, aber wenn wir jetzt dagegen protestieren, hätten wir niemals in der (da dies die gleiche Fremdheit enthält). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Beachten Sie, dass wir nicht einmal ausgenutzt haben, dass das auch von abhängen kann . $f_i$ $n$

Zusammenfassend ist die vorgeschlagene Identität falsch. Wir können uns natürlich auf Konventionen einigen, wie man solche Summen wie die Abkürzung für strenge Berechnungen liest. Solche Konventionen werden jedoch nicht mit der Definition von Landau-Begriffen (zusammen mit dem normalen Missbrauch) vereinbar sein, ohne Kontext und zumindest für Anfänger irreführend - und das ist letztendlich eine Frage des Geschmacks (und der Rücksichtslosigkeit) ?).

Mir ist der Gedanke gekommen, dass wir auch genau das schreiben können , was wir meinen, und trotzdem die Bequemlichkeit der Landau-Begriffe nutzen können. Wir wissen, dass alle Summanden von einer gemeinsamen Funktion stammen, was bedeutet, dass die asymptotischen Grenzen dieselben Konstanten verwenden. Dies geht verloren, wenn wir das in die Summe setzen. Lassen Sie es uns also nicht dort hineinstecken und schreiben $\Theta$

$\qquad \displaystyle \sum_{i=1}^n \frac{2i - 1}{i(i+1)} \in \Theta\left(\sum_{i=1}^n \frac{1}{i}\right) = \Theta(H_n)$

stattdessen. Wenn Sie das außerhalb der Summe setzen, erhalten Sie $\Theta$

eine mathematisch korrekte Aussage und
Ein einfacher Begriff innerhalb des wir uns leicht befassen können (was wollen wir hier, richtig?). $\Theta$

Daher scheint es mir, dass dies sowohl eine korrekte als auch eine nützliche Art ist, die Angelegenheit aufzuschreiben, und daher der Verwendung von Landau-Symbolen innerhalb der Summe vorzuziehen ist, wenn wir sie außerhalb der Summe meinen .

Raphael
quelle

Betrachten Sie . Ich kann (wobei als Konstante verwendet wird), also durch Ihre Argumentation, richtig? Aber diese Summe ist .

\sum_{i}^{n} i

$\sum_i^n i$

f_{i} (n) = i

$f_i(n)=i$

i

$i$

\sum_{i}^{n} i = \sum_{i}^{n} O (1) = O (n)

$\sum_i^n i = \sum_i^n O(1) = O(n)$

O (n^{2})

$O(n^2)$

Xodarap

@Xodarap: Durch meine Argumentation, wie dies die Summe kollabiert nicht funktioniert, weil die innere Kupplung s (die nicht gekoppelt noch ) zu hat die Bedeutung ändern.

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

Raphael

Ich kopple sie nicht an , ich benutze nur die Tatsache, dass . (Und ich nehme auch die Tatsache an, dass .)

n

$n$

\sum_{i}^{n} k = n k

$\sum_i^n k = nk$

n O (f) = O (n f)

$nO(f)=O(nf)$

Xodarap

@Xodarap: Aber Sie nicht haben ein , aber man pro Summand. Wenn die zugrunde liegenden Funktionen verwenden (als konstanter Faktor), müssen Sie erweitern das, und die Summe endet korrekt. Nach meiner Überlegung funktioniert die von Ihnen vorgeschlagene Summierungsregel also eindeutig nicht, während Sie schreiben.

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

Raphael

Wenn ich eine Sequenz , ist jede davon (vorausgesetzt, sie nimmt im Verlauf der Serie nicht zu). Würden Sie sagen, dass das Hinzufügen von von ihnen eine Summe ? Was ist der Unterschied, wenn ich sie nicht als Konstanten beschreibe, sondern als konstante Funktionen ?

5, 1, 3, 2, \dots

$5,1,3,2,\dots$

O (1)

$O(1)$

n

$n$

O (n)

$O(n)$

f_{1} (x) = 5, f_{2} (x) = 1, \dots

$f_1(x)=5,f_2(x)=1,\dots$

Xodarap

-1

Wenn jedes eine Konstante ist, gibt es einige so dass . Also klar Gleiche Idee für wenig Ö. $c_i$ $c_{max}$ $\forall c_i: c_i\leq c_{max}$

\sum c_{i} f (i) \leq \sum c_{m a x} f (i) = c_{m a x} \sum f (i) = O (\sum f (i))

$\sum c_i f(i) \leq \sum c_{max} f(i) = c_{max} \sum f(i) = O\left(\sum f(i)\right)$

Ich denke, das Problem hier ist, dass . Es ist (da es kein so dass ), also ist die Gesamtsumme . Und jeder Term ist , was bedeutet, dass die Gesamtsumme . Daher können mit dieser Methode keine engen Grenzen gefunden werden. $1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$

Ich denke, Ihre Fragen sind:

Ist es akzeptabel, begrenzen, indem man das kleine o jedes Terms und das große o jedes Terms macht und dann mit multipliziert ? (Antwort: Ja) $\sum_i^n f(i)$ $n$
Gibt es eine bessere Methode? (Antwort: Nicht das ich wüsste.)

Hoffentlich kann jemand anderes # 2 klarer beantworten.

EDIT: Wenn Sie Ihre Frage noch einmal durchgehen, denke ich, dass Sie fragen

$\sum_i^n \Theta(f(n)) = \Theta(nf(n))$ ?

Worauf die Antwort ja lautet. In diesem Fall ist jedoch jeder Term nicht von irgendetwas, so dass dieser Ansatz auseinander fällt. $\Theta$

EDIT 2: Sie sagen "Betrachten Sie , dann gibt es kein ". Eindeutig wahr. Wenn Sie sagen, dass eine nicht konstante Funktion von , dann ist es per Definition nicht konstant. $c_i=i$ $c_{max}$ $c_i$ $i$

Beachten Sie, dass wenn Sie es so definieren, nicht , sondern . Wenn Sie "Konstante" als "irgendeine Funktion von " definieren, unterscheiden sich zwei beliebige Funktionen von durch eine "Konstante"! $c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

Vielleicht ist dies eine einfachere Art, sich das vorzustellen: Wir haben die Sequenz . Was ist der kleinste Begriff in dieser Sequenz? Nun, es wird von abhängen . Daher können wir die Begriffe nicht als konstant betrachten. $1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

(Informatiker sind häufig besser mit Big-O vertraut, daher ist es möglicherweise intuitiver zu fragen, ob einen konstant größten Term hat.) $1,\dots,n$

Um Ihren Beweis zu liefern: Sei der kleinste Wert von im Bereich . Dann ist $f(i_{min})$ $f(i)$ $1,\dots,n$

\sum_{i}^{n} f (i) \geq \sum_{i}^{n} f (i_{m i n}) = n f (i_{m i n}) = n o (f (n))

$\sum_i^n f(i) \geq \sum_i^n f(i_{min}) = n f(i_{min}) = n o(f(n))$

Ein analoger Beweis kann für die Obergrenze erbracht werden.

Zuletzt schreiben Sie, dass und geben als Beweis an, dass . Dies ist in der Tat ein Gegenbeweis: Wenn "größer" als , kann es nicht "kleiner" als , was erforderlich ist, damit es . Es kann also nicht . $H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
quelle

1) "..dann gibt es einige so dass ..." - nein, gibt es nicht. Betrachten Sie mit

c_{m a x}

$c_{max}$

(c_{i})_{i \in N}

$(c_i)_{i \in \mathbb{N}}$

c_{i} = i

$c_i = i$ . 2) "Ich glaube nicht, dass " - 3) . Es ist - Das ist falsch. Als , . 4) "(Antwort: Ja)" - solange ich keinen formellen Beweis dafür sehe, glaube ich es nicht. Außerdem ist "Multiplizieren mit " im ausgestellten Fall nicht der Fall.

H_{n} = o (n)

$H_n=o(n)$

H_{n} \in Θ (\ln n)

$H_n \in \Theta(\ln n)$

1 / i \neq Θ (1)

$1/i\not=\Theta(1)$

o (1 / n)

$o(1/n)$

1 / i \geq 1 / n

$1/i \geq 1/n$

1 / i \in Ω (1 / n)

$1/i \in \Omega(1/n)$

n

$n$

Raphael

Ich denke, Sie verpassen den Punkt. Ihr Beweis funktioniert nicht, weil wir möglicherweise nicht in jedem Summanden das gleiche haben und nicht einmal das gleiche für den gleichen Summanden, sondern unterschiedliche . Ich glaube, ich habe es festgenagelt. Ich werde in Kürze eine Antwort verfassen.

f

$f$

n

$n$

Raphael

Ich verstehe immer noch nicht, was du sagst, also bin ich froh, dass du es herausgefunden hast :-)

Xodarap