Что не так с суммами терминов Ландау?

Я написал

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

но мой друг говорит, что это неправильно. Из шпаргалки TCS я знаю, что сумма также называется $H_n$ которая имеет логарифмический рост по $n$ . Таким образом, моя граница не очень четкая, но достаточна для анализа, который мне был нужен.

Что я сделал не так?

Изменить : мой друг говорит, что с тем же рассуждением, мы можем доказать, что

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

Теперь это явно неправильно! Что здесь происходит?

То, что вы делаете, - это очень удобное злоупотребление нотацией.

Некоторые педанты скажут, что то, что вы пишете, является чепухой, поскольку обозначает множество, и вы не можете выполнять арифметические операции над ними так, как вы это делаете.$\mathcal{O}(f)$

Но это хорошая идея - игнорировать этих педантов и предполагать, что обозначает некоторый член набора. Поэтому, когда мы говорим f ( n ) = g ( n ) + O ( n ) , что мы действительно имеем в виду, если это f ( n ) - g ( n ) ∈ O ( n ) . (Примечание: некоторые педанты тоже могут вздрогнуть от этого утверждения, утверждая, что f ( n ) - это число, а $\mathcal{O}(f)$$f(n) = g(n) + \mathcal{O}(n)$$f(n) - g(n) \in \mathcal{O}(n)$$f(n)$$f$ это функция!)

Это делает очень удобным для написания таких выражений, как

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

Это означает, что есть некоторые таким образом, что$f \in \mathcal{O}(n^{1/3})$

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

В вашем случае

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

Вы злоупотребляете этим еще больше, и вам нужно быть осторожным.

Здесь возможны две интерпретации: относится ли к функции n или функции k ?$\mathcal{O}(1)$$n$$k$

Я считаю, что правильное толкование - это интерпретировать его как функцию от .$k$

Если вы попытаетесь думать о нем как о функции , считая его неправильным, это может привести к потенциальным ошибкам, например, если думать, что k есть O ( 1 ), и пытаться записать ∑ n k = 1 k = ∑ n k = 1 O ( 1 $n$$k$$\mathcal{O}(1)$$\sum_{k=1}^{n} k = \sum_{k=1}^{n} \mathcal{O}(1)$

Если вы попытаетесь думать об этом как о функции , то верно, что если f = O ( g ) (как аргумент переходит к ∞ ) и g никогда не равно 0 , то$k$$f = \mathcal{O}(g)$$\infty$$g$$0$

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

Обратите внимание, что в середине мы использовали удобное злоупотребление обозначениями для обозначения того, что для некоторой функции h ∈ O ( g ) сумма равна k n k = 1 h ( k ) . Обратите внимание, что заключительная функция внутри O относится к функции n . Доказательство не так сложно, но вы должны учитывать тот факт, что вы имеете дело с асимптотической верхней границей (т.е. для достаточно больших аргументов), но сумма начинается прямо с 1 .$\mathcal{O}(g(k))$$h \in \mathcal{O}(g)$$\sum_{k=1}^{n} h(k)$$\mathcal{O}$$n$$1$

Если вы попытаетесь представить его как функцию от , то также верно, что если f = O ( g ) (как аргумент идет к ∞ ), то$n$$f = \mathcal{O}(g)$$\infty$

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

Таким образом, ваше доказательство по существу правильно, в любой интерпретации.

То, что вы написали, совершенно правильно. Номер й гармоники действительно находится в множестве O ( n ) .$n$$O(n)$

Доказательство: . $\sum_{i=1}^n \frac{1}{i} \le \ln n + 1 \le 2n = O(n)$$\square$

Верхняя граница не жесткая , но она правильная.$O(n)$

Для второго примера, вы не можете утверждать, что

$$i = O(1)$$

поскольку $i$ зависит от $n$, После нескольких шагов это будет так, что$i>n/2$. A more appropriate way is to say that $i = O(n)$ since indeed, throughout the summation $i$ never exceeds $1\cdot n$. By this reasoning,

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

However the right thing to do is actually use the big-O notation only at the end. Upper bound your summation as tight as you can, and only when your done use the asymptotic notations to avoid these pitfalls.