Por que tem uma interpretação?

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

$\Sigma_{i=1}^{n} O(i)$ é apenas uma única função anônima (de ), mas não é a mesma que , que realmente não tem uma interpretação ".$i$$O(1)+O(2)+\cdots+O(n)$

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+\dots+n =O(n^2)$$O(1)+O(2)+\dots+O(n) = O(n^2)$

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) = 1^2$$S(2) = 1^2 + 2^2$$S(3) = 1^2 + 2^2 + 3^2$$S(4) = 1^2 + 2^2 + 3^2 + 4^2$$1^2 \in O(1)$$2^2 \in O(2)$$3^2 \in O(3)$$4^2 \in O(4)$$S(j)=1^2 + \dots + j^2$$S(j) = O(1) + \dots + O(j)$$S(j) = O(j^2)$$S(n) = n(n+1)(2n+1)/6$$S(n) = \Theta(n^3)$

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(n^2)$$f(n)$$f(n)$$c \ge 0, d\ge 0$$f(n) \le c \cdot n^2$$n\ge d$

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) + \dots + O(n)$$f_1(n) + f_2(n) + \dots + f_n(n)$$f_1(n) \in O(1)$$f_2(n) \in O(2)$$f_n(n) \in 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 .$f_i$$f_i$$f_i$$c_i\ge 0,d_i \ge 0$$f_i(n) \le c_i \cdot i$$n \ge d_i$

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 valor$g(n) = f_1(n) + f_2(n) + \dots + f_n(n)$$d=\max(d_1,d_2,\dots,d_n)$$g(n) \le c_1 \cdot 1 + c_2 \cdot 2 + \dots + c_n \cdot n$$n\ge d$$c=\max(c_1,c_2,\dots,c_n)$$g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$$c$$n$$\max(c_1,c_2,\dots,c_n)$ é 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 .$c$$g(n) \le c \cdot (1+2+\dots+n)$$c$$g(n) \le c \cdot n^2$$g(n) \in O(n^2)$

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.

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:$\sum_{i=1}^{n} O(i)$$O(1) + O(2) + \ldots O(n)$

• $O(1)$ representa um conjunto de funções. Inclui, por exemplo, , , e .$f(n)=1$$f(n)=1/n$$f(n)=n^{1/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 .$\sum_{i=1}^n O(i)$$\sum_{i=1}^n f(i)$$f(i) \in O(i)$$\sum_{i=1}^n 3i-5$$\sum_{i=1}^n O(i)$$O(n^2)$