# Tempo de execução

## Recommended Posts

Boas pessoal, tenho o seguinte algoritmo:

```sum = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
sum = sum+1;
```

A mim da-me T(n) = 4n^2 + 5n + 1 , mas na solução tenho n^2 + n + 1

Como posso calcular o tempo de execução de forma a dar n^2+n+1 ? :S

##### Share on other sites

Boas pessoal, tenho o seguinte algoritmo:

```sum = 0;
for(int i = 1; i < n; i++)
for(int j = 1; j < n; j++)
sum = sum+1;
```

A mim da-me T(n) = 4n^2 +n + 1 , mas na solução tenho n^2 + n + 1

Como posso calcular o tempo de execução de forma a dar n^2+n+1 ? :S

Como é que chegas a esse resultado?

Não respondo a dúvidas por mensagem.

##### Share on other sites

Como é que chegas a esse resultado?

1º instrução: sum = 0; vale: 1 (constante)

2º instrução: for(int i = 1; i < n; i++) vale: 1+ n + n

3º instrução: for(int j = 1; j < n; j++) vale: 1+ n + n

4º instrução: sum =  sum+1; vale: n

Depois:

1 + (2n+1)*(2n+1) + n = 1 + 4n^2 + 2n+2n + n + = 4n^2 + 5n + 1

Dá-me isso.

##### Share on other sites

O teu resultado parece estar certo se analisares ao pormenor.

A solução deve considerar cada for como um n isolado, logo em vez de 1+n+n, contam como n.

Normalmente, na big O notation, ignoram-se as adições e multiplicações por constantes, por isso esse tempo de execução seria O(n²).

##### Share on other sites

O teu resultado parece estar certo se analisares ao pormenor.

A solução deve considerar cada for como um n isolado, logo em vez de 1+n+n, contam como n.

Normalmente, na big O notation, ignoram-se as adições e multiplicações por constantes, por isso esse tempo de execução seria O(n²).

Mas são coisas diferentes, uma é o T(n) que é a expressão sem ignorar as constantes e outra é o O.

E sim, o O seria O(N^2).

Mas e a expressão?

##### Share on other sites

Mas são coisas diferentes, uma é o T(n) que é a expressão sem ignorar as constantes e outra é o O.

E sim, o O seria O(N^2).

Mas e a expressão?

Pois, tens razão.

Uma questão: Eles pedem-te para fazeres uma solução com esse tempo, ou dizem-te que o código que nos mostraste tem esse tempo?

##### Share on other sites

Pois, tens razão.

Uma questão: Eles pedem-te para fazeres uma solução com esse tempo, ou dizem-te que o código que nos mostraste tem esse tempo?

A mim pedem-me a expressão T(n) que dá, segundo eles, n^2 + n + 1 . Não percebo é como chegar a esse resultado.

##### Share on other sites

Nunca tinha ouvido falar de T(n) antes ...

No entanto, ao analisar a tua resposta, notei um erro nos cálculos:

1 + (2n+1)*(2n+1) + n = 1 + 4n^2 + 2n+2n + n + = 4n^2 + 5n + 1

(2n+1)² não dá 4n²+4n, como fizeste, mas sim 4n²+4n+1

Ou seja, no final ficaria:

4n²+5n+2

Mas também pensei mais um pouco no problema, e deu-me resultados diferentes:

sum = 0; -- esta vale um.

for(int i = 1; i < n; i++) -- este for só faz 2n execuções. O int i = 1 vale 1, o i < n vale n, mas o i++ só será feito n-1 vezes (imagina para um valor qualquer de n, como i começa em 1, só irá ser incrementado n-1 vezes). 1+n+n-1 = 2n

for(int j = 1; j < n; j++) -- este for tem o mesmo pormenor do anterior, mas não tens de adicionar o loop anterior? Logo, seria (n-1)(2n) instruções que este faz.

sum = sum+1 -- este não faz sentido valer só n, já que seria executado n² vezes (se aplicarmos o pormenor que falei antes, seria (n-1)²).

Assim, fica com:

1+2n+(n-1)(2n)+(n-1)² = 1 + 2n + 2n²-2n + n²-n-n+1 = 2 - 2n + 3n²

No entanto, continua completamente diferente da solução oficial :S, por isso não faço a mínima idéia de como calcularam.

##### Share on other sites

Nunca tinha ouvido falar de T(n) antes ...

No entanto, ao analisar a tua resposta, notei um erro nos cálculos:

1 + (2n+1)*(2n+1) + n = 1 + 4n^2 + 2n+2n + n + = 4n^2 + 5n + 1

(2n+1)² não dá 4n²+4n, como fizeste, mas sim 4n²+4n+1

Ou seja, no final ficaria:

4n²+5n+2

Mas também pensei mais um pouco no problema, e deu-me resultados diferentes:

sum = 0; -- esta vale um.

for(int i = 1; i < n; i++) -- este for só faz 2n execuções. O int i = 1 vale 1, o i < n vale n, mas o i++ só será feito n-1 vezes (imagina para um valor qualquer de n, como i começa em 1, só irá ser incrementado n-1 vezes). 1+n+n-1 = 2n

for(int j = 1; j < n; j++) -- este for tem o mesmo pormenor do anterior, mas não tens de adicionar o loop anterior? Logo, seria (n-1)(2n) instruções que este faz.

sum = sum+1 -- este não faz sentido valer só n, já que seria executado n² vezes (se aplicarmos o pormenor que falei antes, seria (n-1)²).

Assim, fica com:

1+2n+(n-1)(2n)+(n-1)² = 1 + 2n + 2n²-2n + n²-n-n+1 = 2 - 2n + 3n²

No entanto, continua completamente diferente da solução oficial :S, por isso não faço a mínima idéia de como calcularam.

Pois , acho que me esqueci que a instrução dentro do segundo for depende dos dois for.

Mas dá mal na mesma.. resta saber quem está errado.. :S

##### Share on other sites

Pois , acho que me esqueci que a instrução dentro do segundo for depende dos dois for.

Mas dá mal na mesma.. resta saber quem está errado.. :S

Geralmente atribui-se a cada operação do problema uma constante que é o tempo de execução unitário dessa operação. Por exemplo, a atribuição sum=0 seria T1, a atribuição i=1 seria T2, a comparação i<n seria T3, etc.

Desta forma T(n) resulta numa expressão em que tens somas destas constantes multiplicadas por n^2, n e 1, daí que não faça sentido falar em 4*n^2+n+1 vs n^2+n+1.

Não respondo a dúvidas por mensagem.

##### Share on other sites

Geralmente atribui-se a cada operação do problema uma constante que é o tempo de execução unitário dessa operação. Por exemplo, a atribuição sum=0 seria T1, a atribuição i=1 seria T2, a comparação i<n seria T3, etc.

Desta forma T(n) resulta numa expressão em que tens somas destas constantes multiplicadas por n^2, n e 1, daí que não faça sentido falar em 4*n^2+n+1 vs n^2+n+1.

Mas a solução que tenho, apresenta isso: n^2+n+1 . Agora como se faz não sei..

Tentei perceber por aqui:

`http://www.daniweb.com/forums/thread44665-3.html`

Mas não consigo obter o resultado em questão.

##### Share on other sites

A solução correcta seria:

sum = 0 é executado 1 vez

i = 1 é executado 1 vez

i < n é executado n vezes

i++ é executado n vezes

j = 1 é executado n vezes

j < n é executado n^2 vezes

j ++ é executado n^2 vezes

sum++ é executado n^2 vezes.

Obtens 3n^2 + 3n + 2, SE considerares que uma atribuição, comparação ou incremento têm o mesmo custo. (na realidade, embora dependa do processador, estas instruções costumam ter o mesmo custo)

Como isto não é uma arte exacta, podes querer considerar um for uma única instrução. A análise é equivalente. Por muitas voltas que dês, nunca vais conseguir achar n^2+n+1, a menos que ignores as constantes atrás de cada factor.

##### Share on other sites

A solução correcta seria:

sum = 0 é executado 1 vez

i = 1 é executado 1 vez

i < n é executado n vezes

i++ é executado n vezes

j = 1 é executado n vezes

j < n é executado n^2 vezes

j ++ é executado n^2 vezes

sum++ é executado n^2 vezes.

Obtens 3n^2 + 3n + 2, SE considerares que uma atribuição, comparação ou incremento têm o mesmo custo. (na realidade, embora dependa do processador, estas instruções costumam ter o mesmo custo)

Como isto não é uma arte exacta, podes querer considerar um for uma única instrução. A análise é equivalente. Por muitas voltas que dês, nunca vais conseguir achar n^2+n+1, a menos que ignores as constantes atrás de cada factor.

Mesmo que ignore as constantes atrás de cada factor, a constante isolada é diferente.

##### Share on other sites

Se ignorares as constantes atrás de cada factor ignoras a constante atrás do "1" também.

Eu acho que vou ponderar que a solução que aqui tenho está errada.

Segundo os teus cálculos dá: 3n^2 + 3n + 2 certo?

##### Share on other sites

Sim, mas repara que eu dividi o for nas suas várias instruções e tu consideraste uma instrução única.

Não há solução "mais correcta", há uma "mais aprofundada".

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account

×

• #### Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...

## Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.