Exercícios do livro "Algorithm Design" (Kleinberg, Tardos)

Table of Contents

Capítulo 2

Exercício 9

(a) e (b):

Esse problema é muito legal! Cheguei em uma solução para a letra (b) que me satisfez, mas ainda não consegui provar que está correta. A solução da letra (a) foi bolada pela Cecília. Vou colocar o conteúdo de um chat com o César em que a gente ficou discutindo o problema, tem o meu raciocínio explicadinho:

me: deixa ver se consigo explicar aqui, talvez ajude ate eu entender melhor

me: a grande sacada do k=2 é usar a raiz quadrada. porque? digamos que voce divida o intervalo de N em pedaçinhos menores de tamanho raiz2(n). quantos pedaçinhos teriam? N/raiz2(N), o que é a mesma coisa de raiz2(n).

cesarpalomo: exato

me: logo, eu fico com um número de pedaços em funçao de raiz2(N). no pior caso, eu tenho que testar cada um desses pedaços e o jarro só quebra no último, quando eu tenho que percorrer cada um dos elementos do último pedaçinho. como eu tenho raiz2(N) elementos em cada pedaço, a complexidade do algoritmo fica O( raiz2(N) + raiz2(N) ), o primeiro se refere ao numero de pedacos, o segundo se refere a busca que tenho que fazer

cesarpalomo: exatamente

me: generalizando um pouco, tirando a raiz quadrada e colocando uma raiz qualquer, eu fico com N^(1 - 1/x) para o número de pedaços e N^(1/x) para o numero de passos em cada pedaço

me: fica assim: se eu dividir N em N^(1/x) pedaços, fico com N/N^(1/x) pedaços. fazendo as mágicas da matemática aqui, o total de pedaços fica N^(1-1/x).

me: entao, para o k=2, a melhor escolha é realmente x = 2, em que a complexidade do algoritmo fica O( N^(1 - 1/2) + N^(1/2) )

cesarpalomo: saquei

me: o lance é conseguir encontrar o x para k > 2
se o k = 3, por exemplo, podemos usar x = 1.5
dessa maneira, ficamos com N^(1-1/1.5) pedaços, o que é N^(1/3) pedaços. cada pedaço fica de tamanho N^(1/1.5), ou seja N^(2/3).
em relação ao k=2, o numero de pedacos diminuiu, mas o tamanho de cada pedaco aumentou.
o numero de pedacos era N^(1/2), agora é N^(1/3), diminuiu. o tamanho de cada pedaço era N^(1/2), agora é N^(2/3), aumentou.

cesarpalomo: ta

me: mas o lance é que, agora, como tenho 3 jarras, quando eu encontrar o "pedaço" no qual eu devo buscar, eu não preciso mais percorrer ele um a um.
eu posso pegar esse N^(2/3) e novamente subdividir, como se fosse um subproblema de tamanho N^(2/3) em que eu tenho 2 jarras.
a solução desse subproblema é dividir em N^(2/3 * 1/2) pedaços até encontrar o pedaço e depois fazer uma busca linear neste pedaço, que contem N^(2/3 * 1/2) elementos.
ou seja, a complexidade do subproblema é N^(2/3 * 1/2) = N^(1/3). então a complexidade do problema como um todo foi O( N^(1/3) + complexidade do subproblema ) = O (N^(1/3) + N^(1/3))
acho que ficou um pouco confuso. tá compreensível?

cesarpalomo: eh, preciso dar uma lida com calma pra entender

cesarpalomo: nao ficou confuso
saquei
bom, vc consegue provar por inducao que essa complexidade O( N^(1/x)) se mantém pra outros valores de x?
x na verdade parece que é igual a k, certo?
enfim, vou ver aqui com 4 como ficaria

me: é, acho que a complexidade é O(N^(1/k)) sim. mas nao provei nada ainda nao, so consegui me convencer mesmo.

me: toscamente, seria algo do tipo T(n,k) = O(n^(1/k)) + T( n^(1-1/k), k-1 )
T(n,k) é o custo de testar em uma escada de n degraus com k jarras

cesarpalomo: certo

A dificuldade que estou tendo agora é provar a corretude da complexidade do algoritmo. Mas estou bem convencido que a idéia geral está correta!

A idéia geral do algoritmo é, a cada passo, dividir o total N em "pedaços" de tamanho $N^{1/k}$ e tentarmos resolver o subproblema de tamanho $N^{(k-1)/k}$ com $k-1$ jarras. Poderíamos escrever a recorrência desta maneira:

(1)

$T(x, n) = N^{\frac{x}{k}} + T(1 - \frac{x}{k}, k-1)$

Onde $x$ representa quanto de N ainda estamos tratando na K-ésima jarra. No começo, com as J jarras iniciais, teriamos a resposta com T(1,J). Teríamos então:

(2)

$T(1,J) &=& N^{\frac{1}{J}} + T(1-\frac{1}{J}, J-1) \\ T(1 - \frac{1}{J}, J-1) &=& N^{ (1-\frac{1}{J}) / (J-1) } + T(1 - \frac{1-\frac{1}{J}}{J-1}, J-2) \ \cdots$

Vamos nos concentrar por um momento no expoente de $N$ na segunda iteração do algoritmo:

(3)

$(1 - \frac{1}{J}) / (J-1) \ \frac{J-1}{J} / (J-1) \ \frac{1}{J}$

Que é exatamente o mesmo expoente da primeira iteração! Com isso, podemos ver que o expoente do N não muda a cada iteração, permanecendo sempre constante e de valor $N^{\frac{1}{J}}$ . Dessa maneira, podemos reescrever a recorrência como:

(4)

$T(k) = N^{\frac{1}{J}} + T(k-1)$

Essa maneira de escrever a recorrência simplifica bastante o trabalho de prova da questão. Vamos provar que essa recorrência é uma função $O(N^{\frac{1}{J}})$ . Vamos supor que a recorrência pode ser escrita como $T(k) = k \cdot N^{\frac{1}{J}}$ . O caso base funciona trivialmente, temos $T(2) = 2 \cdot N^{\frac{1}{2}}$ . Supondo então que $T(k-1) = (k-1)*N^{\frac{1}{J}}$ , temos:

(5)

$T(k) &=& k \cdot N^{\frac{1}{J}} \ T(k) &=& N^{\frac{1}{J}} + (k-1) \cdot N^{\frac{1}{J}} \ T(k) &=& N^{\frac{1}{J}} + T(k-1)$

Logo, provamos que o algoritmo tem um tempo computacional limitado assintoticamente por $O(N^{\frac{1}{J}})$ , que é o que queriamos provar: para um número de jarras maior ou igual a 2 o algoritmo é sub-linear em função de N e, quanto mais jarras, mais rápido ele fica em função de N.

Um detalhe muito interessante deste problema é que todo este trabalho poderia ter sido evitado se o enunciado dissesse que o número de jarras era uma função de N. Se fosse, poderiamos utilizar uma busca binária até a última jarra e então fazer uma varredura linear! Muito legal isso!

page_revision: 5, last_edited: 1176227821|%e %b %Y, %H:%M %Z (%O ago)

Edit Tags History Files Print Site tools + Options

NazaWiki

Kung Fu and the art of computer programming

Capítulo 2

Exercício 9