Sumas de términos Landau revisitados

Hice una pregunta (semilla) sobre sumas de términos de Landau antes , tratando de evaluar los peligros del abuso de la notación asintótica en aritmética, con un éxito mixto.

Ahora, aquí nuestro gurú de la recurrencia JeffE hace esencialmente esto:

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

Si bien el resultado final es correcto, creo que esto está mal. ¿Por qué? Si agregamos toda la existencia de constantes implicadas (solo el límite superior), tenemos

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

Ahora, ¿cómo calculamos $c$ partir de $c_1, \dots, c_n$ ? La respuesta es, creo, que no podemos: $c$ tiene que limitarse para todos $n$ pero obtenemos más $c_i$ medida que $n$ crece. No sabemos nada de ellos; $c_i$ puede muy bien depender $i$ , por lo que no podemos suponer un salto: un finita $c$ no pueden existir.

Además, no existe este problema sutil de qué variable tiende a infinito en el lado izquierdo - $i$ o $n$ ? ¿Ambos? Si $n$ (en aras de la compatibilidad), ¿cuál es el significado de $\Theta(1/i)$ , sabiendo que $1 \leq i \leq n$ ? ¿No solo significa $\Theta(1)$ ? Si es así, no podemos vincular la suma mejor que $\Theta(n)$ .

¿Entonces, dónde nos deja eso? ¿Es un error flagrante? ¿Una sutil? ¿O es solo el abuso habitual de la notación y no debemos mirar signos como este fuera de contexto? ¿Podemos formular una regla (rigurosamente) correcta para evaluar (ciertas) sumas de términos de Landau? $=$

Creo que la pregunta principal es: ¿qué es ? Si lo consideramos constante (ya que está dentro del alcance de la suma), podemos construir fácilmente contraejemplos. Si no es constante, no tengo idea de cómo leerlo. $i$

terminology asymptotics landau-notation Rafael
fuente

Esta pregunta sobre matemáticas es una buena lectura sobre aritmética con términos de Landau en general.

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

Espera, Bucky. No escribí ningún resumen con un Theta. Escribí una recurrencia con un Theta en él. ¿Realmente interpretas la recurrencia " " como algo diferente a "Hay una función tal 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 No, la recurrencia no es matemáticamente la misma que la suma, ¡precisamente por la razón que usted describe! La recurrencia tiene exactamente un término Theta, que se refiere inequívocamente a una sola función.

JeffE

Eso no es muy intuitivo , estoy totalmente en desacuerdo, pero creo que es una cuestión de gusto y experiencia.

JeffE

Respuestas:

Me parece correcto en la siguiente convención:

$S_n = \sum_{k=1}^{n} \Theta(1/k)$ es una notación conveniente para

Hay una (como ) tal que $f(x) \in \Theta(1/x)$ $x \to \infty$

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

Por lo tanto, el (o con la notación en esta respuesta ) que obtienes no depende realmente de . $c_i$ $c_k$ $k$

Según esta interpretación, es cierto que . $S_n = \Theta(H_n)$

De hecho, en la respuesta de Jeff, muestra que donde , por lo que es consistente con la interpretación anterior. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

La confusión parece estar surgiendo de "desenrollar" mentalmente la y presumiendo diferentes funciones para cada aparición de ... $\sum$ $\Theta$

Aryabhata
fuente

Jup, pero cada puede tener su propia función y constante. Entonces, esta convención solo funciona con el contexto, es decir, si sabemos que los términos de Landau provienen de una definición algo "uniforme" (en y ) de los sumandos.

Θ

$\Theta$

k

$k$

n

$n$

Raphael

@Raphael: Parece que no tiene sentido desenrollar y luego permitir diferentes : ¡las constantes dependerán de la variable! y se convierte en un uso incorrecto de , suponiendo que la variable es (o en la respuesta anterior). Incluso si asumimos que la variable es , todavía no tiene sentido para mí.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Aryabhata

En principio, todos los puede tener su propia constante, pero en el contexto particular que usted describe , está claro que cada no no tiene su propia constante.

Θ

$\Theta$

Θ

$\Theta$

JeffE

@JeffE: Correcto. Podemos tener múltiples con sus propias constantes, siempre que las constantes sean realmente constantes :-)

Θ

$\Theta$

Aryabhata

@JeffE Entonces, ¿por qué no escribes lo que quieres decir sino que prefieres algo ambiguo / incorrecto? Tenga en cuenta que mi respuesta actualizada ahora propone una forma de hacerlo. Agradecería comentarios sobre eso; Los votos negativos sin razón no me ayudan a entender por qué la gente parece rechazar mi punto.

Raphael

Creo que resolví el problema. En esencia: el uso de términos Landau desacopla la variable de la función summand de la variable en ejecución de la suma. Todavía (queremos) leerlos como idénticos, sin embargo, por lo tanto, la confusión.

Para desarrollarlo formalmente, ¿qué hace

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

¿realmente significa? Ahora supongo que estos dejan - no - hasta el infinito; si dejamos , cada suma se evalúa como (si los sumandos son independientes de por lo tanto, constantes), lo cual es claramente incorrecto. Aquí hay un primer obsequio que señalamos a las cosas crudas: está atado (y constante) dentro de la suma, pero ¿todavía lo dejamos ir al infinito? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

Traduciendo (para el límite superior, el límite inferior funciona de manera similar), obtenemos $(1)$

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

Ahora está claro que la suma y el parámetro están desacoplados: podemos definir fácilmente para que usen como una constante. En el ejemplo de la pregunta, podemos definir y tener $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)$

pero la suma original claramente no evalúa algo en . Ahora, intercambiar por , que es solo un cambio de nombre, en puede parecer extraño porque no es independiente de resp. la suma, pero si nos oponemos a eso ahora , nunca deberíamos haber usado dentro de en primer lugar (ya que eso tiene la misma extrañeza). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Tenga en cuenta que ni siquiera explotamos que también puede depender de . $f_i$ $n$

Para concluir, la identidad propuesta es falsa. Podemos, por supuesto, acordar convenciones sobre cómo leer sumas como la abreviatura de cálculo riguroso. Sin embargo, tales convenciones serán incompatibles con la definición de los términos de Landau (junto con el abuso normal de los mismos), imposibles de entender correctamente sin contexto y al menos engañosas (para principiantes), pero eso es en última instancia una cuestión de gustos (y crueldad) ?)

Se me ocurrió que también podemos escribir exactamente lo que queremos decir y todavía hacer uso de la conveniencia de los términos de Landau. Nosotros sabemos que todos los sumandos provienen de una función común, lo que implica que los límites asintóticos utilizan las mismas constantes. Esto se pierde cuando ponemos el en la suma. Así que no lo pongamos ahí y escribamos $\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)$

en lugar. Poniendo el fuera de la suma resulta en $\Theta$

una declaración matemáticamente correcta y
un término simple dentro del que puede ocuparse fácilmente (que es lo que queremos aquí, ¿verdad?). $\Theta$

Entonces, me parece que esta es una forma correcta y útil de escribir el asunto, y por lo tanto, debería preferirse a usar símbolos de Landau dentro de la suma cuando los queremos decir fuera de ella.

Rafael
fuente

Considere . Puedo definir (usando como constante), por lo tanto, por su razonamiento, ¿verdad? Pero esta suma es .

\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: Por mi razonamiento, el colapso de la suma como este no funciona, porque el acoplamiento del interior s (que no se acopla a ni ) para no cambia el significado.

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

Raphael

No los estoy acoplando a , solo estoy usando el hecho de que . (Y supongo también el hecho de 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: Pero no tienes una , sino una por summand. Si las funciones subyacentes usan (como factor constante), debe expandir eso y la suma termina siendo correcta. Entonces, claramente, según mi razonamiento, la regla de suma que propone no funciona mientras escribe.

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

Raphael

Si tengo una secuencia , cada uno de estos son (siempre que no aumenten a medida que avanza la serie). ¿Diría que agregar de ellos generará una suma ? ¿Cuál es la diferencia si en lugar de ser constantes las describo como funciones 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 cada es una constante, entonces hay alguna tal que . Entonces claramente misma idea por poco 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)$

Creo que el problema aquí es que . Es (ya que no hay tal que ), por lo que la suma total será . Y cada término es , lo que significa que la suma total es . Por lo tanto, no se pueden encontrar límites estrechos con este método. $1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$

Creo que tus preguntas son:

¿Es delimitador haciendo el o pequeño de cada término y el o grande de cada término y luego multiplicando por aceptable? (Respuesta: sí) $\sum_i^n f(i)$ $n$
hay algun metodo mejor? (Respuesta: no que yo sepa)

Esperemos que alguien más pueda responder el # 2 más claramente.

EDITAR: Al revisar su pregunta nuevamente, creo que está preguntando

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

A lo que la respuesta es sí. Sin embargo, en este caso, cada término no es de nada, por lo que ese enfoque se desmorona. $\Theta$

EDITAR 2: Dices "considera , entonces no hay ". Inequívocamente cierto. Si dice que es una función no constante de , entonces, por definición, no es constante. $c_i=i$ $c_{max}$ $c_i$ $i$

Tenga en cuenta que si lo define de esta manera, entonces no es , es . De hecho, si define "constante" como "cualquier función de ", entonces dos funciones de difieren en una "constante". $c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

Tal vez esta sea una manera más fácil de pensar: tenemos la secuencia . ¿Cuál es el término más pequeño en esta secuencia? Bueno, dependerá de . Entonces no podemos considerar los términos como constantes. $1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

(Los informáticos a menudo están más familiarizados con big-O, por lo que podría ser más intuitivo preguntar si tiene un término constante más grande). $1,\dots,n$

Para proporcionar su prueba: deje que sea el valor más pequeño de en el rango . Entonces $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))$

Se puede hacer una prueba análoga para el límite superior.

Por último, escribe que y como prueba da que . De hecho, esto es una prueba contraria: si es "más grande" que , entonces no puede ser "más pequeño" que , que es lo que se requiere para que sea . Entonces no puede ser . $H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
fuente

1) "..entonces hay algo de tal que ..." - no, no lo hay. Considere con . 2) "No creo que " - 3) . Es : eso está mal. Como , . 4) "(Respuesta: Sí)" - mientras no vea una prueba formal de ese hecho, no lo creo. Además, "multiplicar por " no es lo que sucedió en el caso expuesto.

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

Creo que te estás perdiendo el punto. Su prueba no funciona porque es posible que no tengamos la misma en cada sumando, y ni siquiera la misma para la misma suma pero diferente . Creo que lo clavé; Redactaré una respuesta en breve.

f

$f$

n

$n$

Raphael

Todavía no entiendo lo que estás diciendo, así que me alegra que lo hayas descubierto :-)

Xodarap