Was stimmt nicht mit Landau-Begriffen?

Ich schrieb

$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

aber mein freund sagt das ist falsch. Aus dem TCS-Spickzettel weiß ich, dass die Summe auch heißt und logarithmisch in . Meine Schranke ist also nicht sehr scharf, reicht aber für die Analyse aus, für die ich sie brauchte. $H_n$ $n$

Was habe ich falsch gemacht?

Bearbeiten : Mein Freund sagt, dass mit der gleichen Begründung können wir das beweisen

$\qquad \displaystyle \sum\limits_{i=1}^n i = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

Das ist natürlich falsch! Was geht hier vor sich?

asymptotics landau-notation Raphael
quelle

Eine Diskussion über die Tags dieser Frage finden Sie hier .

Raphael

Metadiskussion über die Tag- Algorithmen .

Kaveh

Siehe auch eine konkretere Behandlung eines allgemeinen Beispiels: Was ist die asymptotische Laufzeit dieser verschachtelten Schleife?

Gilles 'SO - hör auf böse zu sein'

Antworten:

Was Sie tun, ist ein sehr bequemer Missbrauch der Notation.

Einige Pedanten werden sagen, dass das, was Sie schreiben, Unsinn ist, da eine Menge bezeichnet und Sie keine arithmetischen Operationen mit ihnen ausführen können, wie Sie es tun. $\mathcal{O}(f)$

Es ist jedoch eine gute Idee, diese Pedanten zu ignorieren und anzunehmen, dass für ein Mitglied der Gruppe steht. Wenn wir also sagen , was meinen wir dann wirklich, wenn . (Hinweis: Einige Pedanten könnten bei dieser Aussage ebenfalls erschauern und behaupten, dass eine Zahl und $\mathcal{O}(f)$ $f(n) = g(n) + \mathcal{O}(n)$ $f(n) - g(n) \in \mathcal{O}(n)$ $f(n)$ $f$ ist die Funktion!)

Dies macht es sehr bequem, Ausdrücke wie zu schreiben

n \leq \sum_{k = 1}^{n} k^{1 / k} \leq n + O (n^{1 / 3})

$n \le \sum_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$

Was dies bedeutet , ist , dass es einige ist , so dass $f \in \mathcal{O}(n^{1/3})$

n \leq \sum_{k = 1}^{n} k^{1 / k} \leq n + f (n)

$n \le \sum_{k=1}^n k^{1/k} \le n + f(n)$

In deinem Fall von

\sum_{k = 1}^{n} \frac{1}{k} = \sum_{k = 1}^{n} Ö (1) = Ö (n)

$\sum_{k=1}^{n} \frac{1}{k} = \sum_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$

Sie missbrauchen es noch weiter und müssen vorsichtig sein.

Hier gibt es zwei mögliche Interpretationen: Bezieht sich auf eine Funktion von oder auf eine Funktion von ? $\mathcal{O}(1)$ $n$ $k$

Ich glaube, die richtige Interpretation besteht darin, sie als Funktion von zu interpretieren . $k$

Wenn Sie denken, es als eine Funktion der versuchen , dachte nicht falsch, könnte es zu potenziellen Täuschungen führen, wie das Denken ist und zu versuchen , schreiben $n$ $k$ $\mathcal{O}(1)$ $\sum_{k=1}^{n} k = \sum_{k=1}^{n} \mathcal{O}(1)$

Wenn Sie versuchen, es als eine Funktion von , dann ist es wahr, dass, wenn (wie das Argument zu geht ) und niemals , dass $k$ $f = \mathcal{O}(g)$ $\infty$ $g$ $0$

S (n) = \sum_{k = 1}^{n} f (k) = \sum_{k = 1}^{n} O (g (k)) = O (\sum_{k = 1}^{n} | g (k) |)

$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(k)) = \mathcal{O}(\sum_{k=1}^{n} |g(k)|)$

Beachten Sie, dass wir in der Mitte den bequemen Missbrauch der Notation zu bedeuten, dass für einige Funktionen die Summe . Beachten Sie, dass sich die letzte Funktion im auf eine Funktion von bezieht . Der Beweis ist nicht so schwierig, aber Sie müssen sich darum kümmern, dass es sich um eine asymptotische Obergrenze handelt (dh für ausreichend große Argumente), aber die Summe beginnt bei . $\mathcal{O}(g(k))$ $h \in \mathcal{O}(g)$ $\sum_{k=1}^{n} h(k)$ $\mathcal{O}$ $n$ $1$

Wenn Sie versuchen, es als eine Funktion von , dann ist es auch wahr, dass wenn (wie das Argument zu geht ) dann $n$ $f = \mathcal{O}(g)$ $\infty$

S (n) = \sum_{k = 1}^{n} f (k) = \sum_{k = 1}^{n} O (g (n)) = O (n g (n))

$S(n) = \sum_{k=1}^{n} f(k) = \sum_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$

Ihr Beweis ist also in jeder Interpretation im Wesentlichen richtig.

Aryabhata
quelle

Fazit: Seien Sie sich bewusst (stellen Sie sicher), dass jedes Vorkommen eines Landau-Symbols eine eigene Konstante einführt (hat) .

Raphael

Was Sie geschrieben haben, ist vollkommen richtig. Die te Harmonische liegt tatsächlich in der Menge . $n$ $O(n)$

Beweis: . $\sum_{i=1}^n \frac{1}{i} \le \ln n + 1 \le 2n = O(n)$ $\square$

Die obere Schranke ist nicht eng , aber korrekt. $O(n)$

JeffE
quelle

Okay: 1 / i ≤ 1 = O (1).

JeffE

Die Sorge richtet sich an das zweite Gleichheitszeichen. Wie überprüfe ich das?

Raphael

Das ist aber auch richtig. Eine Summe von n Termen, von denen jedes O (1) ist, ist tatsächlich O (n).

Suresh

@Suresh Nur wenn die von den

s implizierten Konstanten unabhängig von der Summationsvariablen sind und das hier der Punkt ist (Seed-Frage).

O

$\cal{O}$

Raphael

Der Fehler ist nicht in der zweiten Gleichheit. Der Fehler (im zweiten Ausdruck) liegt darin, wie Sie zu dieser Summe gelangen. Es ist richtig, von

. Es wird behauptet, dass

falsch ist. Mir ist klar, dass dies für alle Beteiligten offensichtlich ist, aber ich denke, dies ist das Problem mit der Frage der Aussaat :)

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

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

i = O (1)

$i = O(1)$

Suresh

Für das zweite Beispiel können Sie nicht behaupten, dass

i = O (1)

$i = O(1)$

da mit variiert . Nach wenigen Schritten ist . Ein geeigneterer Weg ist zu sagen, dass da in der Tat während der gesamten Summation niemals überschreitet . Durch diese Argumentation, $i$ $n$ $i>n/2$ $i = O(n)$ $i$ $1\cdot n$

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

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

Es ist jedoch richtig, die Big-O-Notation nur am Ende zu verwenden. Grenzen Sie Ihre Summe so eng wie möglich ein, und verwenden Sie die asymptotischen Notationen erst dann, wenn Sie fertig sind, um diese Fallstricke zu vermeiden.

Ran G.
quelle