complejidad computacional

Complejidad computacional

1

Complejidad computacional
Definici´ n. Estudio de la eficacia (y/o tiempo de ejecuci´ n) de los alo
o
goritmos.
Definici´ n. Ecuaci´ n de complejidad computacional Es una funci´ n
o
o
o
que para cada valor n proporciona el tiempo m´ ximo que un algoritmo
a
A necesita para encontrar una soluci´ n a una instancia I de longitud n.
o

Unidad b´ sica:operaciones bit.
a

f(n)=n´ mero m´ ximo de operaciones bit requeridas por el algoritmo para
u
a
resolver una instancia de longitud n.
Notaci´ n.
o
Sean f (n) y g(n) funciones; se dice que f es una O-grande de g, y
se denota f (n) = O(g(n)) (o simplemente f = O(g)) si existe una
constante C y un entero n0 tal que f (n) < Cg(n) para todo n ≥ n0 .

Ejemplo.
f (n) = 2n2 + 3n + 4000, g(n) =n2
f (1) = 4005
g(1) = 1
f (2) = 4014
g(2) = 4
f (3) = 4027
g(3) = 9
De ello se deduce que f (n) < 5000 g(n), luego f = O(g)
La notaci´ n f = O(nd ) nos dice que la funci´ n f crece aproximadao
o
mente como elevar a la potencia d.
Por ejemplo, si f = O(n3 ) entonces f (2n) es aproximadamente 8f (n)
(para valores grandes de n).
Definici´ n. Un algoritmo se dice que es de complejidadpolinomial si
o
f (n) = O(p(n)), donde p es un polinomio.
En caso contrario se dice que es de complejidad exponencial.
2

Definici´ n. Se dice que un algoritmo es eficiente si es de complejidad
o
polinomial.
La complejidad de un problema es la complejidad del menor de los algoritmos que lo resuelven. El tiempo de ejecuci´ n de un algoritmo va a
o
depender del tama˜ o de los datos.
nEjemplo.
Factorizar enteros

99336
23 ∗ 3 ∗ 4139
9933699663
32 ∗ 1103744407
993369966355443 3 ∗ 167 ∗ 40731617 ∗ 48679
25 cif ras

0, 012 seg
0, 495 seg
0, 570 seg
0, 645 seg

Por lo tanto tomaremos como input la longitud de los datos.
Si n es un entero, tendr´ [log10 (n)] + 1 d´gitos.
a
ı
Computacionalmente se trabaja en base 2, longitud(n) = [log2 (n)] + 1.
Suma de dos enteros.Sean n y m enteros,
n →
long(n) = k
m → long(m) = l ≤ k

n = ak ak−1 ...a2 a1
m = bl bl−1 ...b2 b1

ak ak−1 ..............................................a2 a1
+
bl bl−1 ........................b2 b1
ak ..al+2 al+1 (al + bl )......(a2 + b2 )(a1 + b1 )
Suma bit a bit: 1 operaci´ n bit.
o

3

0
0
1
1

0
1
0
1

0
1
1
0

Por tanto, el coste de la suma ser´ de koperaciones bit (m´ s, posiblea
a
mente, a lo sumo l operaciones bit-acarreo).
Coste computacional : = O(k + l) = O(2k) = O(k) = O(long(n)).
Operaci´ n lineal en el tama˜ o de las entradas.
o
n
Multiplicaci´ n de dos enteros.
o
Sean n y m enteros,
n →
long(n) = k
m → long(m) = l ≤ k

∗
0
0
...
ak ∗ b l

n = ak ak−1 ...a2 a1
m = bl bl−1 ...b2 b1

ak ak−1..............................................a2 a1
bl bl−1 ........................b2 b1

... ...
0
ak ∗ b1 ak−1 ∗ b1 . . . a2 ∗ b1 a1 ∗ b1
. . . 0 ak−2 ∗ b2 ak−1 ∗ b2 ak−2 ∗ b2 . . . a1 ∗ b2
0
... ...
...
...
... ...
...
...
... ...
a2 ∗ bl
a1 ∗ b l

En cada fila k multiplicaciones bit
0
0
1
1

0
1
0
1

0
0
0
1

Hay exactamente l filas. k ∗ l multiplicaciones bit.

4

Para cada d´gitodel producto hay que hacer l sumas. El producto tiene
ı
longitud k + l.
No total de operaciones bit k ∗ l + (k + l) ∗ l = l(2k + l).
Complejidad computacional del algoritmo de multiplicaci´ n:
o
O(l(2k + l)) = O(k ∗ 3k) = O(3k 2 ) = O(k 2 ).
Existen otros algoritmos para multiplicar.
n = a ∗ 2k/2 + b

m = c ∗ 2k/2 + d

Suponemos n par, en caso contrario se a˜ aden ceros
n
n ∗ m = ac2k+ (ad + bc)2k/2 + b ∗ d =
ac2k + (ac + bd − (a − b)(c − d))2k/2 + bd
Productos necesarios:
• ac
• bd
• (a-b)(c-d)
• Multiplicar por 2r es a˜ adir r ceros
n
3 productos de elementos de tama˜ o k/2.
n
T(k): tiempo para multiplicar dos enteros de longitud k
T (k) = 3T (k/2) + O(k) = 3(3T (k/4) + O(k/2)) + O(k) = . . . =
= 3i T (k/21 ) + 3i−1 O(k/(2i−1 )) + 3i−2 O(k/(2i−2 )) + ... +...