Cálculo do tempo de processamento de algoritmos

Como já sabido, toda operação de computador requer um certo tempo e “esforço” do processador para acontecer. Quando programamos um computador, também é sabido que podemos produzir diversos códigos diferentes para obter o mesmo resultado, de forma similar a chegar a um mesmo resultado em Matemática a partir de distintas formas de fazer a mesma coisa. Contudo, meios diferentes requerem diferentes esforços, sejam nossos ou dos processadores, dando-nos mais ou menos trabalho, exigindo-nos mais ou menos tempo.

Com computadores, estamos falando de algoritmos, estas seqüências lógicas de processamento, se corretamente escolhidas, podem facilitar todo o processo na questão tempo e esforço.

O possível estimar o tempo de execução de algoritmos com a finalidade de saber quais são os melhores quando comparados uns com os outros, e é disso que venho falar.

A performance de um computador é determinada por fatores como:

·          Hardware:

o    Processador usado

o    Memória disponível

o    Disco disponível

·          Software

o    Linguagem e plataforma utilizada

o    Compilador usado

o    Sistema Operacional utilizado

Alguns exemplos de tempos exigidos para tarefas diversas:

• ·    t_{fetch =>} tempo necessário para obter um dado (variável do programa) da memória
• ·    t_{store =>} tempo necessário para salvar um dado na memória (armazená-lo em uma variável)
• ·    t_{+ =>} tempo necessário para executar uma operação de soma. Representações similares existem para as outras 3 operações elementares
• ·    t_{< =>} tempo necessário para realizar a comparação lógica “menor que”. Existe a equivalente para “maior que”
• ·    t_{return =>} tempo necessário para finalizar a execução de um método/função, a partir do momento em que a instrução de código “return” é acionada
• ·    t_{[.] =>} tempo necessário para calcular endereços quando trabalhando-se com “arrays”

Exemplos (Te = tempo de execução):

Exemplo 1: 

y = x;

Te = t_{fetch +} t_store

Exemplo 2:

y = y + 1;

Te = 2(t_fetch) + t₊ + t_store

Primeiro exercício abordado em sala:

O seguinte código foi abordado em sala para calcularmos o tempo de processamento (funciona em C, C++, C# e Java):

// 1) int result = 0;

// 2) for (int i = 1; i <= n; ++i)

// 3) {

// 4)            result += i;

// 5) }

// 6) return result;

Obviamente, o código não está completo, sempre há código necessário tanto antes como depois dessas instruções, em qualquer linguagem, para poder compilar e executar tais instruções.

Vale a pena lembrar também que

result += i;

é uma forma abreviada de escrever

result = result + 1;

Vamos então ao cálculo do tempo de processamento. Resolverei primeiro da forma que o professor fez em sala, e depois, mostrarei uma forma alternativa que pensei aqui que, quando testando, dão o mesmo resultado, e achei bem mais simples do que o método do professor.

Professor:

// 1) t_fetch + t_store

// 2) t_fetch + t_store

// 2) _[2(t_fetch) + t_{<] * (n + 1)}

// 2) _[2(t_fetch) + t₊ + t_{store] * n}

// 4) _[2(t_fetch) + t₊ + t_{store] * n}

// 6) t_fetch + t_{return
________________________________________________ +}

[₆₍t_fetch) + ₂₍t_store) + t_< + ₂₍t₊₎] _{* n} + ₅₍t_fetch) + ₂₍t_store) + t_< + t_return

Minha forma alternativa:

Para facilitar, vou criar variáveis de mais fácil manipulação para nós que estamos acostumados com Álgebra e Polinômios desde o ginásio (primeiro grau):

t_fetch = x

t_store = y

t_< = w

t₊ = z

t_return = s

(n + 1) = a

n = b

Agora, basta trabalhar com x, y , w, z, s, a e b. Veja como fica:

// 1) x + y

// 2) x + y

// 2) (2x + w) * a

// 2) (2x + z + y) * b

// 4) (2x + z + y) * b

// 6) x + s

____________________ + (agrupando termos iguais)

2 (x + y)

a * (2x + w)

2b * (2x + z + y)

x + s

____________________ + (aplicando a distributiva, somando e agrupando os monômios similares)

(2x + 2y) + (2xa + aw) + (4bx + 2bz + 2by) + (x + s) =

3x + 2y + 2xa + aw + 4bx + 2bz + 2by + s (está resolvido)

Agora que a Álgebra foi realizada, trazendo novamente a nomenclatura técnica, fica assim:

3(t_fetch) + 2(t_store) + 2[(n + 1)(t_fetch)] + [(n + 1)(t_<)] + 4 [n(t_fetch)] + 2[n(t₊)] + 2[n(t_store)] + t_return

Para testar os resultados, tanto o do professor quanto o meu, que visualmente não há indicações de serem equivalentes, basta escolher um valor para a variável “n” e verificar o que obtemos. Ambos dão o mesmo resultado, portanto são equivalentes, e vou mostrar isso escolhendo arbitrariamente o valor 4 para a variável “n”. Temos portando 2 resultados:

Professor:

[₆₍t_fetch) + ₂₍t_store) + t_< + ₂₍t₊₎] _{* n} + ₅₍t_fetch) + ₂₍t_store) + t_< + t_return

Meu:

3(t_fetch) + 2(t_store) + 2[(n + 1)(t_fetch)] + [(n + 1)(t_<)] + 4 [n(t_fetch)] + 2[n(t₊)] + 2[n(t_store)] + t_return

Testando a equivalência, para n = 4:

Em ambos os casos, obtemos

29(t_fetch) + 10(t_store) + 5(t_<) + 8(t₊) + t_return

Conclusão:

Confesso que não entendi a última etapa do método do professor, e como preciso de um método para calcular isso (as provas chegarão um dia), acabei pensando na forma acima, que eu acredito simplificar o entendimento durante todo o processo, facilitando para não se perder durante as contas.

Eu acredito que ele fez da forma que fez porque ele quis agrupar o resultado de forma a ser visível através da fórmula

T(n) = t₁ + t₂n

sendo:

t_{1 = 5(}t_fetch) + ₂₍t_store) + t_< + t_return

t_{2 =} [₆₍t_fetch) + ₂₍t_store) + t_< + ₂₍t₊₎] _{* n}

Esta é uma fórmula geral para tal tipo de cálculo dentro de um looping “for”. Caso fosse um looping “for” dentro de outro, também conhecido como “nested loop”, de acordo com o professor, a fórmula seria

T(n) = t₁ + t₂n²

Bom, é isso o que tenho a dizer no momento. Espero que o conteúdo acima sirva para os companheiros de sala e para todos que dependam deste entendimento.

Abraços!