Resolucion apunte 1 - calcular tiempo de ejecucion de un algoritmo T(n) PDF

Preview

Summary

calcular tiempo de ejecucion de un algoritmo T(n)...

Description

Tcond + max(Tentonces , 0) Pmax Tini + j=min (Tcond + Tint + Tincr ) + Tcond Pn−1 = 1 + j=i (1 comp + (T 6 + T 7) + 1 op.mat) + 1 comp = Pn−1 Pn−1 = 1 + j=i (1 + (3 + 2) + 1) + 1 = j=i (7) + 2 = (n − 1 − i + 1) ∗ 7 + 2 = 7(n − i) + 2 = Pmax Tini + j=min (Tcond + Tint + Tincr ) + Tcond Pn−1 Pn−1 = 1 + i=0 (1 comp + (T 4 + T 5) + 1 op.mat) + 1 comp = 1 + i=0 (1 + (T 4 + T 5) + 1) + 1 Pn−1 Pn−1 = 1 + i=0 (1 + (1 + 7n − 7i + 2) + 1) + 1 = i=0 (7n − 7i + 5) + 2 =

=

Pn−1 i=0

(7n) −

Pn−1 i=0

(7i) +

Pn−1 i=0

(5) + 2 = 7

Pn−1 i=0

(n) − 7

Pn−1 i=0

(i) + 5

Pn−1 i=0

(1) + 2 =

Pn−1 i=0 (n) = (n − 1 − 0 + 1) ∗ n = n ∗ n = n Pn−1 i=0 (1) = (n − 1 − 0 + 1) ∗ 1 = n Pn−1 i=0 (i) Pn−1 i=1 (i)

(0 + 1 + ... + n − 1) Pn

i=1 (i)

Pn−1 Pn−1 i=0 (i) = i=1 (i) =

7

Pn−1

(7

i=0 (n) − 7 − 27 )n + ( 72

Pn−1 i=0

(n−1)∗n 2

(i) + 5

= 1 + 2 + ... + n = 1 n 2

= 12 n

Pn−1 i=0

(1) + 2 = 7n − ( 72 n − 72 n) + 5n + 2 =

+ 5)n + 2 = 27 n +

2 + ( 27 n +

n∗(n+1) 2

17 n 2

17 n 2

+2

+ 2) + 1 + 1 = 27 n +

17 n 2

+ 6 = O(n2 )

Tcond + max(Tentonces , 0) =(2 acc.arreglo + 1 comp) + max(T 4, 0) = 3 + 3 = cantrep ∗ (Tcond + Tint ) + Tcond = cantrep ∗ (1 comp + T 3 + T 5) + 1 comp = cantrep (1 + 6 + 2) + 1 = 9 ∗ cantrep + 1 cantrep

1 = 20 2 = 21 4 = 22 8 = 23 n = 2k k+1

k

n = 2k

log2 n = k cantrep = log2 n + 1

9 ∗ cantrep + 1 = 9 ∗ (log2 n + 1) + 1 = 9 ∗ log2 n + 10

1 + 9 ∗ log2 n + 10 = 9 ∗ log2 n + 11 = O(log n)...