complexidade temporal de algoritmos
Enviado: 21 Set 2023 14:47
Teste para analisar a complexidade temporal de algoritmos, especificando como o tempo de execução de um algoritmo aumenta em relação ao tamanho da entrada.
SomaSequencial(nInicio, nFinal)
faz uma série de operações matemáticas, mas não realiza nenhum loop que dependa diretamente do tamanho da entrada. Portanto, a complexidade temporal desta função é constante, ou seja, O(1), porque o tempo de execução não cresce com o tamanho da entrada.
* Mesmo que tenha chamadas de Delay() dentro da função, elas não afetam a complexidade assintótica.
SomaSequencialConvencional(nInicio, nFinal)
essa função usa um loop "for" que itera do valor inicio ao valor final. O número de iterações deste loop depende diretamente do tamanho da entrada, ou seja, é proporcional ao valor final - inicio. Portanto, a complexidade temporal desta função é linear, ou seja, O(n), onde "n" é igual a final - inicio.
* Portanto, para a função SomaSequencialConvencional, a complexidade temporal é O(n), onde "n" é o tamanho da entrada (ou seja, final - inicio).
** a notação Big O descreve o comportamento assintótico do algoritmo, ou seja, como o tempo de execução aumenta em relação ao tamanho da entrada quando a entrada se torna muito grande. Neste caso, a função SomaSequencial é mais eficiente em termos de complexidade temporal do que a função SomaSequencialConvencional.
SomaSequencial(nInicio, nFinal)
faz uma série de operações matemáticas, mas não realiza nenhum loop que dependa diretamente do tamanho da entrada. Portanto, a complexidade temporal desta função é constante, ou seja, O(1), porque o tempo de execução não cresce com o tamanho da entrada.
* Mesmo que tenha chamadas de Delay() dentro da função, elas não afetam a complexidade assintótica.
SomaSequencialConvencional(nInicio, nFinal)
essa função usa um loop "for" que itera do valor inicio ao valor final. O número de iterações deste loop depende diretamente do tamanho da entrada, ou seja, é proporcional ao valor final - inicio. Portanto, a complexidade temporal desta função é linear, ou seja, O(n), onde "n" é igual a final - inicio.
* Portanto, para a função SomaSequencialConvencional, a complexidade temporal é O(n), onde "n" é o tamanho da entrada (ou seja, final - inicio).
** a notação Big O descreve o comportamento assintótico do algoritmo, ou seja, como o tempo de execução aumenta em relação ao tamanho da entrada quando a entrada se torna muito grande. Neste caso, a função SomaSequencial é mais eficiente em termos de complexidade temporal do que a função SomaSequencialConvencional.
Código: Selecionar todos
// compilar com: hbmk2 teste_calc.prg
#define MODO_DEBUG .T.
FUNCTION Main()
LOCAL x
nInicio := 1
aFinal := {10, 50, 100}
CLS
? "Teste de Calculos Sequencial"
? "calcular o tempo gasto pelas funcoes"
FOR x := 1 TO LEN(aFinal)
? REPLICAT("-",80)
? "Soma Sequencial: 1-" + ALLTRIM(STR(aFinal[x]))
nTempo1 = TIME()
? "Resultado da Soma Sequencial: " + ALLTRIM(STR(SomaSequencial(nInicio,aFinal[x])))
nTempo2 = TIME()
? "Tempo Gasto: " + ElapTime(nTempo1, nTempo2)
? REPLICAT(".",80)
nTempo1 = TIME()
? "Resultado da Soma Sequencial Convencional: " + ALLTRIM(STR(SomaSequencialConvencional(nInicio,aFinal[x])))
nTempo2 = TIME()
? "Tempo Gasto: " + ElapTime(nTempo1, nTempo2)
NEXT
? REPLICAT("-",80)
RETURN Nil
FUNCTION Delay()
iif(MODO_DEBUG,INKEY(.2),INKEY(.01))
RETURN Nil
FUNCTION SomaSequencial(nInicio, nFinal)
nReserva := 0
Delay()
nTotTermos := (nFinal - nInicio) +1
Delay()
if ((nTotTermos % 2) != 0)
nReserva := nFinal
Delay()
nFinal--
Delay()
nTotTermos--
Delay()
endif
nMetade := nTotTermos / 2
Delay()
nDoisTermos := nFinal + nInicio
Delay()
nResultado := (nMetade * nDoisTermos) + nReserva
Delay()
RETURN nResultado
FUNCTION SomaSequencialConvencional(nInicio, nFinal)
nResultado := 0
Delay()
FOR n := nInicio to nFinal
nResultado += n
Delay()
NEXT
RETURN nResultado