Exercício 1.14
Mariana Bravo
Acho que várias pessoas pularam esse exercício, ou pelo menos não comitaram suas respostas... podemos discutir a solução?
A parte de desenhar a árvore nem tinha muita graça, mas e quanto ao consumo de tempo e espaço? A única resposta que eu achei era bem diferente da minha...
Para mim, o número de passos é O(n^5), ou melhor, O(n^k) onde k é quantos tipos de moedas temos disponíveis. Isso pq ao acrescentar um tipo de moeda, vc tem O(n) vezes a quantidade de operações que vc tinha antes.
Seguindo a dica do livro de que o espaço é proporcioanal à altura da árvore, então o espaço seria O(n). Só a tal dica que não é muito clara pra mim...
Mari
--
Mariana Bravo
Celular: (11) 9179 7796
msn: mar...@gmail.com
Skype: marivbravo
Andrei Formiga
>
> A parte de desenhar a árvore nem tinha muita graça, mas e quanto ao consumo
> de tempo e espaço? A única resposta que eu achei era bem diferente da
> minha...
>
> Para mim, o número de passos é O(n^5), ou melhor, O(n^k) onde k é quantos
> tipos de moedas temos disponíveis. Isso pq ao acrescentar um tipo de moeda,
> vc tem O(n) vezes a quantidade de operações que vc tinha antes.
>
> Seguindo a dica do livro de que o espaço é proporcioanal à altura da árvore,
> então o espaço seria O(n). Só a tal dica que não é muito clara pra mim...
>
> Mari
Acho que essas análises de tempo e espaço estão um pouco estranhas.
Primeiro acho que é interessante estabelecer quem é o N, o tamanho do
problema. É o amount? O número de tipos de moedas? Os dois (N e M)?
Só olhando o código de count-change (a função cc, na verdade), já dá
para desconfiar que a complexidade temporal (número de passos) não é
polinomial, ou seja, O(n^k) para algum k.
Quanto ao espaço, ele é proporcional à altura da árvore porque a
estrutura de chamadas recursivas segue a ordem de uma busca em
profundidade na árvore. Se é proporcional à altura, tudo depende de
como a altura da árvore e N se relacionam (para isso é preciso
estabelecer claramente quem é N). Se N é o número de nós na árvore, a
altura da árvore é proporcional a um logaritmo de N cuja base depende
do grau da árvore (quantos filhos tem cada nó). No caso de análise
assintótica, pode-se usar qualquer base então fica O(logN). Mas a não
ser que o N seja definido de uma maneira meio estranha, ele não será o
número de nós da árvore.
Essas considerações são meio vagas de propósito, já que a idéia é não
dar as respostas de vez. Mas espero que ajude a melhorar as análises.
--
[]s, Andrei Formiga
Mariana Bravo
Acho que essas análises de tempo e espaço estão um pouco estranhas.
Primeiro acho que é interessante estabelecer quem é o N, o tamanho do
problema. É o amount? O número de tipos de moedas? Os dois (N e M)?
N é o que pede no enunciado do exercício no meu entendimento, ou seja, N é a quantia a ser trocada, a variável amount da função count-change.
Chamei o número de tipos de moedas de K.
Só olhando o código de count-change (a função cc, na verdade), já dá
para desconfiar que a complexidade temporal (número de passos) não é
polinomial, ou seja, O(n^k) para algum k.
Minha intuição era justamente o contrário... Cada chamada a cc gera duas outras chamadas a cc e o parâmetro amount diminui de valor bem devagar, a passos constantes definidos pelos valores das moedas disponíveis - ou seja, demora pra chegar nos casos base.
Quanto ao espaço, ele é proporcional à altura da árvore porque a
estrutura de chamadas recursivas segue a ordem de uma busca em
profundidade na árvore.
Essa é uma interpretação interessante!
Se é proporcional à altura, tudo depende de
como a altura da árvore e N se relacionam (para isso é preciso
estabelecer claramente quem é N). Se N é o número de nós na árvore, a
altura da árvore é proporcional a um logaritmo de N cuja base depende
do grau da árvore (quantos filhos tem cada nó). No caso de análise
assintótica, pode-se usar qualquer base então fica O(logN). Mas a não
ser que o N seja definido de uma maneira meio estranha, ele não será o
número de nós da árvore.
Considerando N a quantia a ser trocada, então a altura da árvore é O(N), correto?