Jump to content

Tempo de execução


vasco16
 Share

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

Obrigado.

Link to comment
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

Obrigado.

Como é que chegas a esse resultado?

Não respondo a dúvidas por mensagem.

Link to comment
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.

Link to comment
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²).

Link to comment
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?

Link to comment
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?

Link to comment
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.

Link to comment
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.

Link to comment
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

Link to comment
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.

Link to comment
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.

Link to comment
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.

Link to comment
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.

Link to comment
Share on other sites

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

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • 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.