Por que tem uma interpretação?

8

No CLRS (nas páginas 49-50), qual é o significado da seguinte declaração:

Σi=1nO(i) é apenas uma única função anônima (de ), mas não é a mesma que , que realmente não tem uma interpretação ".iO(1)+O(2)++O(n)

kesari
fonte
Eu tentei formular sua pergunta com mais precisão; Observe também que temos suporte ao látex aqui para que você possa escrever uma matemática bem formatada. Convido você a ser mais específico: o que exatamente é confuso? Qual parte está causando problemas? (Talvez você possa editar o título da pergunta de acordo).
Juho
1
Indiscutivelmente, a soma expandida também não tem uma interpretação; você deve escrever do começo. O()
Raphael
1
Alguém pode explicar o significado pretendido de ? Soma de funções da ordem " "? Isso faz pouco sentido, como . Soma de funções indexadas por de alguma ordem? i=1nO(i)niO(i)=O(1)ni
Yves Daoust

Respostas:

12

Como , é tentador sugerir que ... mas isso não é de fato válido. O motivo é que pode haver uma constante diferente para cada termo na soma.1+2++n=O(n2)O(1)+O(2)++O(n)=O(n2)

Um exemplo

Deixe-me dar um exemplo. Considere as somas , , , e assim por diante. Observe que , , , e assim por diante para cada termo no soma. Portanto, seria razoável escrever na forma . Então, podemos concluir que ? Não. De fato, , então .S(1)=12S(2)=12+22S(3)=12+22+32S(4)=12+22+32+4212O(1)22O(2)32O(3)42O(4)S(j)=12++j2S(j)=O(1)++O(j)S(j)=O(j2)S(n)=n(n+1)(2n+1)/6S(n)=Θ(n3)

Se isso não ajudar, vamos tentar o seguinte desenvolvimento matemático mais preciso:

Uma formalização

Lembre-se de que a interpretação de, digamos, é que é um conjunto de funções não negativas (ou seja, o conjunto de funções modo que exista constantes tal que para todos ).O(n2)f(n)f(n)c0,d0f(n)cn2nd

O mais próximo que podemos chegar de uma interpretação de é que é o conjunto de funções da forma tal que , , ..., .O(1)+O(2)++O(n)f1(n)+f2(n)++fn(n)f1(n)O(1)f2(n)O(2)fn(n)O(n)

Mas agora as constantes para cada podem ser diferentes. Assim, cada é uma função não negativa modo que existem constantes com para todos os .fififici0,di0fi(n)ciindi

Agora, dado isso, o que podemos dizer sobre ? Não é muito útil. Sabemos que existe uma constante tal que para todos os . Agora, o que podemos dizer sobre essa soma? Bem, a resposta é que não podemos dizer nada. Pode ser arbitrariamente grande. É tentador deixar e dizer que ... mas isso não está realmente correto, pois precisamos de um único valor constante de que funcione para todos os , e o valorg(n)=f1(n)+f2(n)++fn(n)d=max(d1,d2,,dn)g(n)c11+c22++cnnndc=max(c1,c2,,cn)g(n)c(1+2++n)cn2=O(n2)cnmax(c1,c2,,cn) é uma função de , não uma constante.n

Portanto, pode não haver constante tal que ; pode não haver constante tal que . Não há garantia de que .cg(n)c(1+2++n)cg(n)cn2g(n)O(n2)

Para mais leitura

Consulte https://math.stackexchange.com/q/86076/14578 e os termos Soma de Landau revisitados para outras perguntas que tratam desse problema geral.

DW
fonte
2
TLDR: você deseja que todos sejam iguais mas eles não são formalmente. fO(_)
Raphael
1

A razão pela qual o comentário do CLRS é confuso é que, tecnicamente, é definido como . O que realmente está acontecendo é que o CLRS está abusando da notação por uma questão de simplicidade:i=1nO(i)O(1)+O(2)+O(n)

  • O(1) representa um conjunto de funções. Inclui, por exemplo, , , e .f(n)=1f(n)=1/nf(n)=n1/n
  • Quando você escreve você está tecnicamente adicionando dois conjuntos e com uma operação de sumset . Quando isso é feito com mais de um número constante de termos, pode levar a comportamentos inesperados, como o DW explica claramente em outra resposta.O(1)+O(2)O(1)O(2)

Em vez disso, o CLRS gostaria que você interpretasse como onde a função genérica . Por exemplo, eles escreveriam que é ou .i=1nO(i)i=1nf(i)f(i)O(i)i=1n3i5i=1nO(i)O(n2)

Ari Trachtenberg
fonte
Essa explicação não está certa. Não há nada errado em adicionar . Isso é bem definido. é um conjunto de funções, é um conjunto de funções e, quando são conjuntos de funções, é normalmente entendido como o conjunto de funções . Isso é o que normalmente se pretende quando adicionamos duas notações de grande oh, e tudo funciona bem desde que você adicione apenas dois (ou um número constante de) símbolos de grande oh. O problema é que o número de adendos não é constante, como explicado na minha resposta. O(1)+O(2)O(1)O(2)S,TS+T{f(n)+g(n):f(n)S,g(n)T}
DW
Concordo que esta é a definição comum de adição de conjuntos e que está bem definida, embora eu não pense que é isso que se entende em uso comum. Como você disse corretamente na sua resposta acima, o uso da adição definida em mais de um número constante de termos leva a problemas.
Ari Trachtenberg
Prefiro definir O (f (n)) como um elemento anônimo de um determinado conjunto de funções, em vez do próprio conjunto. Então significa " para alguma função tal que ...", enquanto significa " para algumas funções forma que ... ". Totalmente não é a mesma coisa. iO(i)if(i)fO(1)+O(2)++O(n)f1(1)+f2(2)++fn(n)f1,f2,,fn
JeffE 11/06