Soma dos termos do Landau revisitados

Eu fiz uma pergunta (inicial) sobre somas dos termos do Landau antes , tentando avaliar os perigos de abusar da notação assintótica em aritmética, com sucesso misto.

Agora, aqui o nosso guru da recorrência JeffE faz essencialmente isso:

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

Embora o resultado final esteja correto, acho que está errado. Por quê? Se adicionarmos toda a existência de constantes implícitas (apenas o limite superior), teremos

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

Agora, como calculamos $c$ de $c_1, \dots, c_n$ ? A resposta é, creio eu, que não pode: $c$ tem para com destino a todos os $n$ , mas temos mais $c_i$ como $n$ cresce. Não sabemos nada sobre eles; $c_i$ pode muito bem depender de $i$ , então não podemos assumir um limite: um finito $c$ pode não existir.

Além disso, existe esta questão sutil de qual variável vai para o infinito no lado esquerdo - $i$ ou $n$ ? Ambos? Se $n$ (por uma questão de compatibilidade), qual é o significado de $\Theta(1/i)$ , sabendo que $1 \leq i \leq n$ ? Isso não significa apenas $\Theta(1)$ ? Nesse caso, não podemos limitar a soma melhor que $\Theta(n)$ .

Então, onde isso nos deixa? É um erro flagrante? Um sutil? Ou é apenas o abuso usual de notação e não devemos olhar sinais como este fora de contexto? Podemos formular uma regra (rigorosamente) correta para avaliar (certas) somas dos termos do Landau? $=$

Eu acho que a questão principal é: o que ? Se considerarmos constante (como está dentro do escopo da soma), podemos facilmente criar contra-exemplos. Se não for constante, não tenho ideia de como lê-lo. $i$

terminology asymptotics landau-notation Rafael
fonte

Esta pergunta sobre math.SE é uma boa leitura sobre aritmética com os termos Landau em geral.

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 aí, Bucky. Eu não escrevi nenhum resumo com um Theta nele. Eu escrevi uma recorrência com um Theta nele. Você realmente interpreta a recorrência "

" como algo diferente de "Existe uma função

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 19/07/12

@ Rafael Não, a recorrência não é matematicamente igual à soma, exatamente pelo motivo que você descreve! A recorrência tem exatamente um termo teta, que sem ambiguidade se refere a uma única função.

21812 JeffE

Isso não é muito intuitivo - discordo totalmente, mas acho que é uma questão de gosto e experiência.

21812 JeffE

Respostas:

Parece certo para mim na seguinte convenção:

é uma notação conveniente para $S_n = \sum_{k=1}^{n} \Theta(1/k)$

Existe um (como ) tal que $f(x) \in \Theta(1/x)$ $x \to \infty$

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

Assim, o (ou com a notação nesta resposta ) que você obtém não depende realmente de . $c_i$ $c_k$ $k$

Sob essa interpretação, é realmente verdade que . $S_n = \Theta(H_n)$

De fato, na resposta de Jeff, ele mostra que onde , por isso é consistente com a interpretação acima. $T(k+1) = f(k) + T(k)$ $f \in \Theta(1/k)$

A confusão parece estar surgindo mentalmente de "desenrolar" o e presumindo funções diferentes para cada ocorrência de ... $\sum$ $\Theta$

Aryabhata
fonte

Sim, mas todo

pode ter sua própria função e constante. Portanto, essa convenção funciona apenas com o contexto, isto é, se soubermos que os termos de Landau resultam de uma definição "uniforme" (em

) dos summands.

Θ

$\Theta$

k

$k$

n

$n$

Raphael

@Raphael: Parece sem sentido desenrolar e depois permitir

diferente : as constantes dependerão da variável! e torna-se uma utilização incorrecta de

, assumindo a

variável é

(ou

em resposta acima). Mesmo se assumirmos que a variável é

, ela ainda parece sem sentido para mim.

f_{i}

$f_i$

Θ

$\Theta$

Θ

$\Theta$

i

$i$

k

$k$

n

$n$

Aryabhata

Em princípio, todos os

pode ter sua própria constante, mas no contexto particular que você descreve , é claro que todos os

que não têm a sua própria constante.

Θ

$\Theta$

Θ

$\Theta$

19412 JeffE

@ Jeff: Certo. Podemos ter múltiplos

com as suas próprias constantes, enquanto as constantes são realmente constante :-)

Θ

$\Theta$

Aryabhata

@ Jeff Então, por que você não escreve apenas o que quer dizer, mas prefere algo ambíguo / errado? Observe que minha resposta atualizada agora propõe uma maneira de fazer isso. Eu apreciaria comentários sobre isso; votos negativos sem motivo não me ajudam a entender por que as pessoas parecem rejeitar meu argumento.

Raphael

Acho que resolvi o problema. Em essência: o uso de termos Landau desacopla a variável da função summand da variável em execução da soma. Nós ainda (queremos) lê-los como idênticos, porém, portanto, a confusão.

Para desenvolvê-lo formalmente, o que faz

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

realmente significa? Agora, suponho que estes deixem - não - ao infinito; se deixarmos , a cada esses avalia soma (se o summands são independentes da e, portanto, constante) que é claramente errada. Aqui está a primeira oferta que devemos dar a coisas cruas: é limitado (e constante) dentro da soma, mas ainda a deixamos ir ao infinito? $\Theta$ $i$ $n$ $n \to \infty$ $\Theta(n)$ $n$ $i$

Traduzindo (para o limite superior, o limite inferior funciona da mesma forma), obtemos $(1)$

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

Agora é claro que o sum- e parameter- são dissociados: podemos facilmente definir o para que eles usem como uma constante. No exemplo da pergunta, podemos definir $i$ $i$ $f_i$ $i$ e tem $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)$

mas a soma original claramente não avalia a algo em . Agora, trocar por - que é apenas uma renomeação - no pode parecer estranho porque não sou independente de resp. a soma, mas se objetarmos a isso agora , nunca deveríamos ter usado dentro de em primeiro lugar (pois isso mantém a mesma estranheza). $\Theta(H_n) = \Theta(\log n)$ $j$ $i$ $\Theta$ $i$ $n$ $i$ $\Theta$

Note que nem sequer explorar que o pode também depender . $f_i$ $n$

Para concluir, a identidade proposta é falsa. É claro que podemos concordar com convenções sobre como ler somas como abreviação de cálculos rigorosos. No entanto, tais convenções serão incompatíveis com a definição dos termos do Landau (juntamente com o abuso normal deles), impossíveis de entender corretamente sem contexto e enganosas (para iniciantes) pelo menos - mas isso é, em última análise, uma questão de gosto (e crueldade) ?).

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

$\Theta$

uma declaração matematicamente correta e
$\Theta$

Portanto, parece-me que essa é uma maneira correta e útil de escrever a questão, e, portanto, deve ser preferida ao usar símbolos Landau dentro da soma, quando os queremos fora dela.

Rafael
fonte

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

Θ

$\Theta$

i

$i$

n

$n$

n

$n$

n

$n$

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

$\sum_i^n k = nk$

n O (f) = O (n f)

$nO(f)=O(nf)$

f

$f$

f_{i}

$f_i$

f_{i}

$f_i$

i

$i$

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$

-1

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

$1/i\not=\Theta(1)$ $o(1/n)$ $\epsilon$ $\forall i: 1/i>\epsilon$ $no(1/n)=o(1)$ $O(1)$ $O(n)$ . Portanto, nenhum limite restrito pode ser encontrado nesse método.

Eu acho que suas perguntas são:

$\sum_i^n f(i)$ $n$
Há um método melhor? (Resposta: Não que eu saiba.)

Espero que alguém possa responder # 2 mais claramente.

EDIT: Olhando para sua pergunta novamente, acho que você está perguntando

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

$\Theta$

$c_i=i$ $c_{max}$ $c_i$ $i$

$c_i i$ $\Theta(i)$ $\Theta(i^2)$ $i$ $i$

$1,\frac{1}{2},\dots,\frac{1}{n}$ $n$

$1,\dots,n$

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

Uma prova análoga pode ser feita para o limite superior.

$H_n = o(n)$ $H_n = \Theta(\log n)$ $H_n$ $n$ $\log n$ $\Theta(\log n)$ $o(n)$

Xodarap
fonte

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$

f

$f$

n

$n$

Eu ainda não entendo o que você está dizendo, então estou feliz que você tenha entendido :-) #

1128 Xodarap