Soma dos termos do Landau revisitados

10

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:

i=1nΘ(1i)=Θ(Hn)

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

i=1nci1icHn.

Agora, como calculamos c de c1,,cn ? A resposta é, creio eu, que não pode: c tem para com destino a todos os n , mas temos mais ci como n cresce. Não sabemos nada sobre eles; ci pode muito bem depender de i , então não podemos assumir um limite: um finito cpode 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 Θ(1/i) , sabendo que 1in ? Isso não significa apenas Θ(1) ? Nesse caso, não podemos limitar a soma melhor que Θ(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

Rafael
fonte
2
Esta pergunta sobre math.SE é uma boa leitura sobre aritmética com os termos Landau em geral.
Raphael
4
ΘC = max ( c 1 , c 2 , , c n )c=min(c1,c2,,cn)C=max(c1,c2,,cn)
5
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 f Θ x ( x 1 / x ) tal que t ( n ) = f ( n ) + t (t(n)=Θ(1/n)+t(n1)fΘx(x1/x) "?t(n)=f(n)+t(n1)
JeffE 19/07/12
4
@ 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
2
Isso não é muito intuitivo - discordo totalmente, mas acho que é uma questão de gosto e experiência.
21812 JeffE

Respostas:

5

Parece certo para mim na seguinte convenção:

é uma notação conveniente paraSn=k=1nΘ(1/k)

Existe um (como x ) tal quef(x)Θ(1/x)x

.Sn=k=1nf(k)

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

Sob essa interpretação, é realmente verdade que .Sn=Θ(Hn)

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

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

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 k e n ) dos summands. Θ kn
Raphael
2
@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 é i (ou k em resposta acima). Mesmo se assumirmos que a variável é n , ela ainda parece sem sentido para mim. fiΘΘikn
Aryabhata
3
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. ΘΘ
19412 JeffE
2
@ Jeff: Certo. Podemos ter múltiplos com as suas próprias constantes, enquanto as constantes são realmente constante :-)Θ
Aryabhata
11
@ 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
1

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

Sni=1nΘ(f(i))(1)

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

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

f1,,fnΘ(f). Sni=1nfi(i)

Agora é claro que o sum- e parameter- i são dissociados: podemos facilmente definir o f i para que eles usem i como uma constante. No exemplo da pergunta, podemos definir f i ( j ) = i 1iifiie temfi(j)=i1jΘ(1/j)

i=0nfi(i)"="i=0nΘ(1/j)=i=0nΘ(1/i)

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

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

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) ?).

Θ

i=1n2i1i(i+1)Θ(i=1n1i)=Θ(Hn)

Θ

  • uma declaração matematicamente correta e
  • Θ

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
inifi(n)=iiini=inO(1)=O(n)O(n2)
Θinn
nink=nknO(f)=O(nf)
ffifii
5,1,3,2,O(1)nO(n)f1(x)=5,f2(x)=1,
-1

cicmaxci:cicmax

cif(i)cmaxf(i)=cmaxf(i)=O(f(i))

1/iΘ(1)o(1/n)ϵi:1/i>ϵ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:

  1. inf(i)n
  2. 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

inΘ(f(n))=Θ(nf(n))

Θ

ci=icmaxcii

ciiΘ(i)Θ(i2)ii

1,12,,1nn

1,,n

f(imin)f(i)1,,n

inf(i)inf(imin)=nf(imin)=no(f(n))

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

Hn=o(n)Hn=Θ(logn)HnnlognΘ(logn)o(n)

Xodarap
fonte
cmax(ci)iNci=iHn=o(n)HnΘ(lnn)1/iΘ(1)o(1/n)1/i1/n1/iΩ(1/n)n
fn
Eu ainda não entendo o que você está dizendo, então estou feliz que você tenha entendido :-) #
1128 Xodarap