Esclarecendo $\sum_{h=0}^{\lfloor lg(n) floor}\lceil\frac{n}{2^{h+1}} ceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n) floor}\frac{h}{2^h})$ em BUILD-MAX-HEAP

Question

Eu estava indo o texto de Introdução a Algoritmos de Cormen et.al.De onde eu vim através de um passo a análise do tempo de complexidade do $BUILD-MAX-HEAP$ procedimento.

O procedimento é o seguinte:

BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

Agora, os autores afirmam derivar um aspecto vinculado ao se observar que o tempo para $MAX-HEAPIFY$ para ser executado em um nó varia de acordo com a altura do nó na árvore, e as alturas de a maioria de nós são pequenos.O mais apertado de análise baseia-se nas propriedades que um $n$-elemento de pilha tem altura $\lfloor lg (n) floor$ e no mais $\lceil \frac{n}{2^{h+1}} ceil$ nós de qualquer altura $h$.

Assim,$$\sum_{h=0}^{\lfloor lg (n) floor} \lceil \frac{n}{2^{h+1}} ceil O(h)= O(n \sum_{h=0}^{\lfloor lg (n) floor} \frac{h}{2^h}) \ldots ag 1$$

Agora ele está no passo acima que eu estou enfrentando o problema. Como são os autores obter a expressão no RHS usando o LHS tão simplesmente(como se intuitivamente). No entanto, eu não parecem compartilhar a mesma intuição.

Agora a altura máxima de qualquer nó é a altura da raiz que é $\lfloor lg (n) floor$.Agora deixe-nos encontrar um limite para o valor mínimo possível da fração $\frac{n}{2^{h+1}}$ ,que ocorre quando $a=\lfloor lg (n) floor$

Assim, $$\frac{n}{2^{\lfloor lg (n) floor+1}} = \frac{n}{2.2^{\lfloor lg (n) floor}}\geqslant\frac{n}{2.2^{lg (n)}}=\frac{n}{2n}=\frac{1}{2} \ldots ag 2$$

A partir de agora a etapa de análise pelos autores em (1) eles estão assumindo o

$$\lceil \frac{n}{2^{h+1}} ceil \leqslant c.\frac{n}{2^h}, c>0 $$

Agora, até onde eu sei, a partir de matemática,

$$\lceil \frac{n}{2^{h+1}} ceil \lt \frac{n}{2^{h+1}}+1$$

E para a forma como os autores trabalhados , deve ser a situação como abaixo,

$$\lceil \frac{n}{2^{h+1}} ceil \lt \frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

Assim, $$\frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$

$$\iff 1 \leqslant c.\frac{n}{2^{h}}-\frac{n}{2^{h+1}}$$

$$\iff 1 \leqslant \frac{n}{2^{h+1}}(2c-1)$$

$$\iff \frac{n}{2^{h+1}}\geqslant \frac{1}{2c-1} \ldots ag 3 $$

Agora para (3) de acordo com (2) devemos ter,

$$2.c-1 \geqslant 2 \iff c \geqslant \frac{3}{2}$$

Agora é que a única linha em (1) valor este muito esforço ou é a situação que o passo é trivial ou intuitiva de que podemos apenas mentalmente fazer o passo.Se ele é o último, por favor, me ilumine com tal intuição..

Mesmo nessa resposta aqui que $\frac{n}{2^{h+1}}\lt\frac{n}{2^{h}}$ é intuitivo, mas que $1\lt\frac{n}{2^{h}}$ não é bem intuitivo e requer o uso de (2) eu me sinto

Answer 1

Desde $h \leq \lfloor \lg n floor$, temos $2^h \leq n$, e assim por $n/2^{h+1} \geq 1/2$.Portanto, $$ \left\lceil \frac{n}{2^{h+1}} ight ceil \leq \frac{n}{2^{h+1}} + 1 = \frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq \frac{n}{2^{h+1}} + 2 \, \ frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}.$$ (Na verdade, se você estiver com mais cuidado, em seguida, você pode substituir $3$ por $2$.)

Mais geralmente, se $x \geq c > 0$ em seguida, $\lceil x ceil = S(x)$, onde o oculto constante depende $c$.