Dúvida 'pequena' - L9 PROBLEM 3

[José Casadei]

Alguém pode ajudar?

Dúvida no terceiro exercício da aula 9. O exercício dá um código e pede para calcular o número de passos para rodar o código (na melhor situação, uma lista vazia. Na pior situação, uma lista longa).

Abaixo, colei o código. Depois, colei a resposta e a explicação, dadas pelo MIT. As anotações em vermelho ao lado do código com o símbolo # foram feitas por mim, para tentar resolver. As anotações em vermelho em negrito, na explicação do MIT, mostram minha dúvida.

Minha resposta seria: 3*n^2 + 2

A resposta do MIT é: 3*n^2 + n + 2

def program1(L):

    multiples = []                                                    # 1 step

    for x in L:                                                          # 1 step x n times

        for y in L:                                                      # 3 steps x n times

            multiples.append(x*y)

    return multiples                                                  # 1 step

 

In this case we go through the loop for x in L ntimes. Every time through this loop, we execute an assignment of a value to x, and then the inner loop for y in L. The assignment takes 1 step on each iteration; how many steps does the inner loop take on each iteration?

The inner loop has three operations (assignment of a value to y, x*y, and list appending). So the inner loop executes 3*n times on each iteration of the outer loop. Thus the nested loop structure is executed n * (3*n + 1) = 3*n**2 + n times! (Aqui, eu não entendo porque o MIT acrescenta +1 aos três passos existentes no loop interno, o que resultará em n*1 (ou somente n) na resposta final)

Adding in two steps (for the first assignment statement, and the return statement) we see that in the worst case, this program executes 3*n**2 + n + 2 steps.

[Marco Túlio Pires]

Zé,

Loop interno:

- Atribuição de valor para y (1)

- Multiplicação x * y (1)

- acrescentar valor à lista (1)

Logo, loop interno = 1 + 1 + 1 = 3 steps. Se a lista for grande, quer dizer que teremos esses 3 steps executados N vezes. Ou seja: 3*n.

Agora, loop externo:

- Atribuição do valor para x (1)

- Executar todo o loop interno (3*n)

Ou seja, pra executar UMA VEZ o loop externo (o que inclui o loop interno), temos 3*n + 1.

E se essa bagaça toda é executada N vezes, temos:

(3*n + 1) * n

Que é a mesma coisa que escrever:

3*n**2 + n

Ajudou?

--
Você recebeu essa mensagem porque está inscrito no grupo quot;Aprendendo a Programar com o MIT e a Escola de Dados" dos Grupos do Google.
Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para programadedados20...@googlegroups.com.
Para postar nesse grupo, envie um e-mail para programaded...@googlegroups.com.
Acesse esse grupo em http://groups.google.com/group/programadedados2014_01.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/programadedados2014_01/3be9bd1a-ea61-47f4-8379-080bfd41c47f%40googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

--

Marco Túlio Pires :: journogeek :: @mtrpires

[José Casadei]

A confusão que estou fazendo é que, no meu entendimento, esse UMA VEZ já faz parte do loop externo, ou seja, seria a mesma coisa.

Para mi, logo:

(+1) seria redundante porque já há Atribuição do valor para x (1) quando rodamos o loop externo.

Mas ok, vou adotar como regra...

Abs

Zé

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para programadedados2014_01+unsub...@googlegroups.com.

Para postar nesse grupo, envie um e-mail para programaded...@googlegroups.com.
Acesse esse grupo em http://groups.google.com/group/programadedados2014_01.
Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/programadedados2014_01/3be9bd1a-ea61-47f4-8379-080bfd41c47f%40googlegroups.com.
Para mais opções, acesse https://groups.google.com/d/optout.

[Marco Túlio Pires]

Imagine que o loop externo será executado só uma vez. Como ficaria?

- atribuição do valor de x (1 steps)

- executar o loop interno (3n steps)

Ou seja, pra executar o loop externo apenas uma vez, seria (3n + 1) steps.

Só que você não executa ele só uma vez no pior cenário. Você executa ele n vezes. Por isso:

n * (3n + 1)

que é:

3n^2 + n

Para cancelar inscrição nesse grupo e parar de receber e-mails dele, envie um e-mail para programadedados20...@googlegroups.com.

Para postar nesse grupo, envie um e-mail para programaded...@googlegroups.com.
Acesse esse grupo em http://groups.google.com/group/programadedados2014_01.

Para ver essa discussão na Web, acesse https://groups.google.com/d/msgid/programadedados2014_01/d215ee2a-266e-4d2e-b498-b13101463b42%40googlegroups.com.

Para mais opções, acesse https://groups.google.com/d/optout.

[Marco Túlio Pires]

Na verdade, se você executar o loop externo só uma vez fica assim:

- atribuição do valor de x (1 steps)

- executar o loop interno (3 steps)

Ou seja, pra executar o loop externo apenas uma vez, seria (3) + 1 steps.

Só que você não executa ele só uma vez no pior cenário. Você executa ele n vezes. Então são n vezes o loop externo e n vezes o loop interno. Por isso:

n * (3*n + 1)

que é:

3n^2 + n

[José Casadei]

Beleza, compreendido!

Caguetaram seu aniversário!

Feliz aniversário! Como presente, não pergunto mais nada ... rs

Abs

[Marco Túlio Pires]

haha obrigado!!

Dúvidas são sempre bem-vindas! Keep them coming!!

Abração