Espaço e Número de passos
Mariana Bravo
Achei a explicação do livro sobre o espaço e número de passos consumidos por um processo bem confusa/incompleta/difícil de entender... Alguém mais achou isso? Vamos bolar algo melhor?
Com base no modelo de substituição, eu diria que:
- O número de passos consumidos pelo processo é (proporcional ao) o número de substituições + o número de operações "primitivas" (+,*,etc) feitas ao expandir uma expressão.
- O espaço consumido pelo processo é (proporcional ao) tamanho da maior linha ao expandir uma expressão.
Vocês concordam com essas explicações?
Como vcs entendem/explicam esses conceitos?
Mari
--
Mariana Bravo
Celular: (11) 9179 7796
msn: mar...@gmail.com
Skype: marivbravo
Conrado Porto Lopes Gouvêa
> - O número de passos consumidos pelo processo é (proporcional ao) o número
> de substituições + o número de operações "primitivas" (+,*,etc) feitas ao
> expandir uma expressão.
> - O espaço consumido pelo processo é (proporcional ao) tamanho da maior
> linha ao expandir uma expressão.
>
> Vocês concordam com essas explicações?
> Como vcs entendem/explicam esses conceitos?
>
Embora aparente ser correto, o ruim deste esquema é que ele é pouco
prático (vai ser chato ficar contando todas as operações...). Me
parece que o conceito de "número de passos" e "espaço consumido" é
meio vago justamente para facilitar a contagem (embore concorde que
não seja muito didático).
Pra passos, acho que basta contar as operações que dependem do valor
sendo analisado. Por exemplo, uma certa função que recebe um parâmetro
n e ela itera por um número que depende de n, então cada "iteração" é
um passo. Não importa, por exemplo, se cada iteração realiza 5 ou 10
somas, no final o número de passos "absoluto" (como no seu esquema)
vai cair na mesma complexidade.
Na questão de espaço, acho que a sua análise é uma boa. Acredito que
mais pra frente vai começar manipulação de listas, aí tem que levar
isso em conta também...
Conrado
Mariana Bravo
2009/8/5 Mariana Bravo <mar...@gmail.com>:
> - O número de passos consumidos pelo processo é (proporcional ao) o númeroEmbora aparente ser correto, o ruim deste esquema é que ele é pouco
> de substituições + o número de operações "primitivas" (+,*,etc) feitas ao
> expandir uma expressão.
> - O espaço consumido pelo processo é (proporcional ao) tamanho da maior
> linha ao expandir uma expressão.
>
> Vocês concordam com essas explicações?
> Como vcs entendem/explicam esses conceitos?
>
prático (vai ser chato ficar contando todas as operações...). Me
parece que o conceito de "número de passos" e "espaço consumido" é
meio vago justamente para facilitar a contagem (embore concorde que
não seja muito didático).
Pra passos, acho que basta contar as operações que dependem do valor
sendo analisado. Por exemplo, uma certa função que recebe um parâmetro
n e ela itera por um número que depende de n, então cada "iteração" é
um passo. Não importa, por exemplo, se cada iteração realiza 5 ou 10
somas, no final o número de passos "absoluto" (como no seu esquema)
vai cair na mesma complexidade.
Tem razão, aí é que entra o "proporcional a". O que importa é a quantidade de operações que dependem de n, como você disse. Mas "operações" pode ser tanto substituições quanto operações primitivas, e o número exato não importa...
Na questão de espaço, acho que a sua análise é uma boa. Acredito que
mais pra frente vai começar manipulação de listas, aí tem que levar
isso em conta também...
Então, como ainda não temos as listas, por enquanto o espaço é proporcional à quantidade de "operações pendentes" que o interpretador tem que manter em memória, pode-se dizer assim?
Mari
Conrado
Renato Cunha
On Tue, Aug 11, 2009 at 12:21:07PM -0300, Mariana Bravo wrote:
> > Na questão de espaço, acho que a sua análise é uma boa. Acredito que
> > mais pra frente vai começar manipulação de listas, aí tem que levar
> > isso em conta também...
>
> Então, como ainda não temos as listas, por enquanto o espaço é proporcional
> à quantidade de "operações pendentes" que o interpretador tem que manter em
> memória, pode-se dizer assim?
Ao menos é isso o que eu assumi. Minhas análises estão baseadas no número de
operações pendentes na pilha para o espaço, como você disse.
[]'s,
--
Renato Cunha <http://renatocunha.com>
Blog: http://valedotrovao.com
"Whatever happens, happens"