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:
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
.
Agora, como calculamos de ? A resposta é, creio eu, que não pode: tem para com destino a todos os , mas temos mais como cresce. Não sabemos nada sobre eles; pode muito bem depender de , então não podemos assumir um limite: um finito pode não existir.
Além disso, existe esta questão sutil de qual variável vai para o infinito no lado esquerdo - ou ? Ambos? Se (por uma questão de compatibilidade), qual é o significado de , sabendo que ? Isso não significa apenas ? Nesse caso, não podemos limitar a soma melhor que .
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.
Respostas:
Parece certo para mim na seguinte convenção:
é uma notação conveniente paraSn=∑nk=1Θ(1/k)
Assim, o (ou com a notação nesta resposta c k ) que você obtém não depende realmente de k .ci ck k
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 Θ ...∑ Θ
fonte
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
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?Θ i n n→∞ Θ(n) n i
Traduzindo (para o limite superior, o limite inferior funciona da mesma forma), obtemos(1)
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 ⋅ 1i i fi i e temfi(j)=i⋅1j∈Θ(1/j)
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) j i Θ i n i Θ
Note que nem sequer explorar que o pode também depender n .fi 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) ?).
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.
fonte
Eu acho que suas perguntas são:
Espero que alguém possa responder # 2 mais claramente.
EDIT: Olhando para sua pergunta novamente, acho que você está perguntando
Uma prova análoga pode ser feita para o limite superior.
fonte