Práctica 2: Complejidad (Algoritmos III)
De Cuba-Wiki
Ejercicio 02.01:
log(2,n)
Ejercicio 02.02:
No. Base 1 requiere espacio O(n), y las demas O(log n)
Ejercicio 02.03:
a)
b)
c)
Ejercicio 02.04:
a)
i. f = n <= 1*n (todo n) -> f es O(n)
ii. f = 3*n^2 + 7*n + 4 <= 4*n^2 (n>=8) -> f es O(n^2)
iii.f = n^i <= 1*n^j (todo n) <=> i < j -> f es O(n^j) <=> i < j
iv. f = n*log n <= 1*n^2 (todo n) -> f es O(n^2)
b)
Sup. Ex. k en R / n! <= k* r^n <=> n!/r^n <= k. Pero lim{n->∞} n!/r^n = ∞ (ABS)
Ejercicio 02.05:
a) O(1)
b) O(d)
c) O(n)
d) O(n^2)
Ejercicio 02.06:
a)
b)
c)
Ejercicio 02.07:
a)
int bin2dec(string s) res = 0; para i = |s|-1..0 si (s[i]=='1') res += 2^i; devolver res;
b) No. Podria no parar nunca
c) Si
d)
string dec2bin(int n) res = <>; while (n != 0) si (n % 2 != 0) res = '1' + res; sino res = '0' + res; devolver res;
Ejercicio 02.08:
a)
b)
c)
Ejercicio 02.09:
a)
b)
c)
d)
Ejercicio 02.10:
a)
b)
c)
d)
e)
Ejercicio 02.11:
Ejercicio 02.12:
Ejercicio 02.13:
a)
b)
c)
Ejercicio 02.14:
a)
b)
c)
d)
e)
f)
Ejercicio 02.15:
a)
b)
c)
Ejercicio 02.16:
a)
b)
c)
d)
e)
Ejercicio 02.17:
a)
b)
c)
Ejercicio 02.18:
a)
b)
c)
Ejercicio 02.19:
a)
b)
c)
Ejercicio 02.20:
Ejercicio 02.21:
Ejercicio 02.22:
a)
Algoritmo:
1.si (actual != b) avanzo 2.sino volver 1 lugar hacia atras 3.si (cinta == ultimo guardado) tachamoa cinta con b nos movemos al anterior y guardamos (pero si es blanco ir a SI) volvemos a 1 sino ir a NO
b)