Sums of Landau terms revisited

J'ai posé une question (initiale) sur des sommes de termes Landau auparavant , essayant de mesurer les dangers d'abuser de la notation asymptotique en arithmétique, avec un succès mitigé.

Maintenant, ici, notre gourou de la récurrence, JeffE, fait essentiellement ceci:

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

Bien que le résultat final soit correct, je pense que c'est faux. Pourquoi? Si l'on ajoute à toute l'existence de constantes implicites (uniquement la borne supérieure), on a

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

Maintenant, comment calculer $c$ partir de $c_1, \dots, c_n$ ? La réponse est, je crois, que nous ne pouvons pas: $c$ doit se limiter à tout $n$ mais nous obtenons plus de $c_i$ mesure que $n$ croît. Nous ne savons rien d'eux; $c_i$ peut très bien dépendre de $i$ , donc on ne peut pas supposer de borne: un fini $c$ peut ne pas exister.

De plus, il y a ce problème subtil dont la variable va à l'infini sur le côté gauche - $i$ ou $n$ ? Tous les deux? Si $n$ (pour des raisons de compatibilité), quelle est la signification de $\Theta(1/i)$ , sachant que $1 \leq i \leq n$ ? Cela ne signifie-t-il pas seulement $\Theta(1)$ ? Si c'est le cas, nous ne pouvons pas mieux la somme que $\Theta(n)$ .

Alors, où en sommes-nous? C'est une erreur flagrante? Un subtil? Ou est-ce simplement l'abus habituel de la notation et nous ne devrions pas regarder les signes comme celui-ci hors de leur contexte? Pouvons-nous formuler une règle (rigoureusement) correcte pour évaluer (certaines) sommes de termes Landau? $=$

Je pense que la question principale est: qu'est-ce que ? Si nous la considérons constante (car elle est dans le cadre de la somme), nous pouvons facilement construire des contre-exemples. S'il n'est pas constant, je ne sais pas comment le lire. $i$

terminology asymptotics landau-notation Raphael
la source

Cette question sur math.SE est une bonne lecture sur l'arithmétique avec les termes de Landau en général.

Raphael

\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)$

Tiens bon, Bucky. Je n'ai pas écrit de résumé avec un Thêta dedans. J'ai écrit une récurrence avec un Thêta dedans. Interprétez-vous vraiment la récurrence " " comme autre chose que "Il y a une fonction tel que "?

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 Non, la récurrence n'est pas mathématiquement la même que la somme, précisément pour la raison que vous décrivez! La récurrence contient exactement un terme Thêta, qui se réfère sans ambiguïté à une seule fonction.

JeffE

Ce n'est pas très intuitif - je ne suis pas du tout d'accord, mais je pense que c'est une question de goût et d'expérience.

JeffE

Réponses:

Me semble bien dans la convention suivante:

$S_n = \sum_{k=1}^{n} \Theta(1/k)$ est une notation pratique pour

Il y a un (comme ) tel que $f(x) \in \Theta(1/x)$ $x \to \infty$

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

Ainsi les (ou avec la notation dans cette réponse ) que vous obtenez, ne dépendent pas vraiment de . $c_i$ $c_k$ $k$

Selon cette interprétation, il est en effet vrai que . $S_n = \Theta(H_n)$

En fait, dans la réponse de Jeff, il montre que où , donc c'est cohérent avec l'interprétation ci-dessus. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

La confusion semble provenir du "déroulement" mental de la et de la présomption de fonctions différentes pour chaque occurrence de ... $\sum$ $\Theta$

Aryabhata
la source

Jup, mais chaque peut avoir sa propre fonction et constante. Cette convention ne fonctionne donc qu'avec le contexte, c'est-à-dire si l'on sait que les termes de Landau découlent d'une définition quelque peu "uniforme" (en et ) des sommets.

Θ

$\Theta$

k

$k$

n

$n$

Raphael

@Raphael: Il semble insensé de dérouler puis d'autoriser différents : les constantes dépendront alors de la variable! et cela devient une utilisation incorrecte de , en supposant que la variable est (ou dans la réponse ci-dessus). Même si nous supposons que la variable est , elle me semble toujours vide de sens.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Aryabhata

En principe, chaque peut avoir sa propre constante, mais dans le contexte particulier que vous décrivez , il est clair que chaque n'a pas sa propre constante.

Θ

$\Theta$

Θ

$\Theta$

JeffE

@JeffE: C'est vrai. Nous pouvons avoir plusieurs avec leurs propres constantes, tant que les constantes sont vraiment constantes :-)

Θ

$\Theta$

Aryabhata

@JeffE Alors pourquoi n'écrivez-vous pas simplement ce que vous voulez dire mais préférez quelque chose d'ambigu / de faux? Notez que ma réponse mise à jour propose maintenant un moyen de le faire. J'apprécierais des commentaires à ce sujet; les votes descendants sans raison ne m'aident pas à comprendre pourquoi les gens semblent rejeter mon argument.

Raphael

Je pense avoir résolu le problème. En substance: l'utilisation des termes de Landau dissocie la variable de la fonction summand de la variable courante de la somme. Nous (les voulons) toujours les lire comme identiques, cependant, donc la confusion.

Pour le développer formellement,

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

Vraiment méchant? Maintenant je suppose que ces laissent - pas - à l'infini; si nous laissons , chaque somme de ce type est évaluée à (si les sommets sont indépendants de et donc constants), ce qui est clairement faux. Voici un premier cadeau qui nous permet de grossir les choses: est lié (et constant) à l'intérieur de la somme, mais la laisser aller à l'infini? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

En traduisant (pour la borne supérieure, la borne inférieure fonctionne de manière similaire), nous obtenons $(1)$

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

Maintenant, il est clair que la somme et le paramètre sont découplés: on peut facilement définir les pour qu'ils utilisent comme constante. Dans l'exemple de la question, nous pouvons définir et avoir $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)$

mais la somme d'origine n'évalue clairement pas quelque chose dans . Maintenant, échanger pour - qui n'est qu'un changement de nom - dans le peut sembler étrange car n'est pas indépendant de resp. la somme, mais si nous nous y opposons maintenant , nous n'aurions jamais dû utiliser à l'intérieur du en premier lieu (car cela a la même étrangeté). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Notez que nous n'avons même pas exploité que le peut aussi dépendre de . $f_i$ $n$

Pour conclure, l'identité proposée est fausse. Nous pouvons, bien sûr, convenir de conventions sur la façon de lire des sommes telles que l'abréviation d'un calcul rigoureux. Cependant, de telles conventions seront incompatibles avec la définition des termes Landau (ainsi que leur abus normal), impossible à comprendre correctement sans contexte et trompeur (pour les débutants) au moins - mais c'est finalement une question de goût (et de cruauté) ?).

Il m'est venu à l'esprit que nous pouvons également écrire exactement ce que nous voulons dire tout en utilisant la commodité des termes Landau. Nous savons que tous les sommets proviennent d'une fonction commune, ce qui implique que les bornes asymptotiques utilisent les mêmes constantes. Ceci est perdu lorsque nous mettons le dans la somme. Alors ne le mettons pas dedans et écrivons $\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)$

au lieu. Mettre dehors de la somme résulte en $\Theta$

une déclaration mathématiquement correcte et
un terme simple dans le nous pouvons facilement traiter (ce que nous voulons ici, non?). $\Theta$

Il me semble donc que c'est à la fois une manière correcte et utile d'écrire la question, et devrait donc être préférée à l'utilisation des symboles Landau à l' intérieur de la somme quand nous les entendons à l' extérieur .

Raphael
la source

Considérez . Je peux définir (en utilisant comme constante), donc par votre raisonnement, non? Mais cette somme est .

\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: Par mon raisonnement, l' effondrement de la somme comme cela ne fonctionne pas, parce que le couplage intérieur s (qui ne sont pas couplés à ni ) à ne modifie le sens.

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

Raphael

Je ne les relie pas à , j'utilise simplement le fait que . (Et je suppose aussi que .)

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: Mais vous n'avez un , mais par summand. Si les fonctions sous-jacentes utilisent (comme facteur constant), vous devez développer cela, et la somme finit par être correcte. Donc, clairement, par mon raisonnement, la règle de sommation que vous proposez ne fonctionne pas pendant que vous écrivez.

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

Raphael

Si j'ai une séquence , chacun d'eux est (à condition qu'ils n'augmentent pas à mesure que la série progresse). Diriez-vous que l'ajout de générera une somme ? Quelle est la différence si au lieu d'être des constantes, je les décris comme des fonctions constantes ?

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

Si chaque est une constante, alors il y a un tel que . Alors clairement Même idée pour peu o. $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)$

Je pense que le problème ici est que . C'est (puisqu'il n'y a pas de tel que ), donc la somme globale sera . Et chaque terme est , ce qui signifie que la somme globale est . Donc, aucune limite stricte ne peut être trouvée à partir de cette méthode. $1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$

Je pense que vos questions sont:

Le bornage en faisant le petit o de chaque terme et le grand o de chaque terme puis en multipliant par acceptable? (Réponse: oui) $\sum_i^n f(i)$ $n$
Existe-t-il une meilleure méthode? (Réponse: pas que je sache.)

J'espère que quelqu'un d'autre pourra répondre plus clairement au # 2.

EDIT: En examinant à nouveau votre question, je pense que vous demandez

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

À qui la réponse est oui. Dans ce cas cependant, chaque terme n'est pas de quoi que ce soit, de sorte que cette approche s'effondre. $\Theta$

EDIT 2: Vous dites "considérez , alors il n'y a pas ". Vrai sans équivoque. Si vous dites que est une fonction non constante de , alors il est, par définition, non constant. $c_i=i$ $c_{max}$ $c_i$ $i$

Notez que si vous le définissez de cette façon, alors n'est pas , c'est . En effet, si vous définissez "constante" comme signifiant "toute fonction de ", alors deux fonctions de diffèrent par une "constante"! $c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

C'est peut-être une façon plus simple d'y penser: nous avons la séquence . Quel est le plus petit terme de cette séquence? Eh bien, cela dépendra de . Nous ne pouvons donc pas considérer les termes comme constants. $1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

(Les informaticiens connaissent souvent mieux le big-O, il peut donc être plus intuitif de demander si a un terme constant le plus grand.) $1,\dots,n$

Pour fournir votre preuve: soit la plus petite valeur de dans la plage . Alors $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))$

Une preuve analogue peut être faite pour la borne supérieure.

Enfin, vous écrivez que et comme preuve donnez que . Il s'agit en fait d'une contre-épreuve: si est "plus grand" que , il ne peut pas être "plus petit" que , ce qui est requis pour qu'il soit . Donc ça ne peut pas être . $H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
la source

1) "..alors il y a des tels que ..." - non, il n'y en a pas. Considérons avec . 2) "Je ne pense pas que " - 3) . C'est - C'est faux. Comme , . 4) "(Réponse: Oui)" - tant que je ne vois pas de preuve formelle de ce fait, je n'y crois pas. D'ailleurs, "multiplier par " n'est pas ce qui s'est passé dans le cas exposé.

c_{m a x}

$c_{max}$

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

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

c_{i} = i

$c_i = i$

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

Je pense que tu ne comprends pas. Votre preuve ne fonctionne pas car nous n'avons peut-être pas le même dans chaque summand, et même pas le même pour le même summand mais différent . Je pense que je l'ai cloué; Je rédigerai une réponse sous peu.

f

$f$

n

$n$

Raphael

Je ne comprends toujours pas ce que vous dites, donc je suis content que vous ayez compris :-)

Xodarap