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
