Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 76: |
Línea 76: |
| </pre> | | </pre> |
| <br>b) | | <br>b) |
| <br>c) usando Teorema Maestro tenemos: T(n) = 2 * T(n/2) + n^2, que entra en el tercer caso, quedándonos: O(n^2) | | <br>c) O(n log n) |
|
| |
|
| ==Ejercicio 03.04== | | ==Ejercicio 03.04== |
Línea 287: |
Línea 287: |
|
| |
|
| ==Ejercicio 03.09== | | ==Ejercicio 03.09== |
| <br>a) Primero pensemos en la funcion recursiva. TIP: veamos la version booleana y luego si sale, se puede hacer la version con los operandos. | | <br>a) |
| | | <br>b) |
| i es el indice del vector v de valores a los cuales se les van a aplicar los operandos.
| |
|
| |
| f(i,w) = { true si i=1 y W=v1
| |
| false si i = 1 y W !=v1
| |
| f(i-1,w-vi) || f(i-1, w/ri) || f(i-1, nroot(w)) //hacemos un or
| |
| | |
| <br>b) Se puede ahcer pseudo-polinomial en O(nW) | |
| | |
| ==Ejercicio 03.10== | | ==Ejercicio 03.10== |
|
| |
|
Línea 586: |
Línea 578: |
| ==Ejercicio 03.12== | | ==Ejercicio 03.12== |
| ==Ejercicio 03.13== | | ==Ejercicio 03.13== |
| <br>a) no es optimo ya que se puede realizar con solo 2 operaciones. Insertando una 'c' entre las 'b' y borrando la ultima 'a'. | | <br>a) |
| <br>b) | | <br>b) |
| <pre> | | <pre> |