ALGORITMOS

Question 1

¿En qué consiste la técnica de Backtracking?

Answer 1

Técnica de diseño de algoritmos basada en explorar todo el “árbol” de posibles soluciones (prueba y error) –> Fuerza Bruta
NOTA: Una posible optimización para no “repetir” calculos seria Ramificación y Poda

Question 2

¿Qué requisito tiene el algoritmo de la búsqueda binaria y que complejidad computacional tiene?

Answer 2

a) Que los datos estén ordenados (array, arbol,…)
b) O(log n)

Question 3

Ordene, de mas eficiente a menos, estas complejidades: n!, nlogn, n^2, 2^n

Answer 3

n log(n) - n^2 - 2^n - n!

Question 4

¿En qué consiste cada iteración del algoritmo Radix-Sort?

Answer 4

En distribuir en las colas/urnas los números segun un determinado digito (unidades,decenas,centenas,… o al reves)
NOTA: Necesitamos de un “espacio” adicional

Question 5

De una definición de la propiedad de “estabilidad” en los algoritmos de ordenación

Answer 5

Mantiene el orden relativo original para claves iguales

Question 6

¿En qué consiste el algoritmo de inserción binaria?

Answer 6

Que mediante búsqueda binaria obtenemos el lugar donde insertar el elemento a ordenar en cada iteración

Question 7

¿El algoritmo de ordenación BubleSort siempre presenta un complejidad O(n^2)?

Answer 7

No, en el mejor de los casos seria O(n) -> Se da cuenta si los datos ya están ordenados

Question 8

¿Qué requisito necesita cualquier función recursiva?

Answer 8

Una condición de parada (CASO BASE)

Question 9

¿Cómo explicaría el mecanismo que se produce en una llamada a una función?

Answer 9

Cuando se llama a una funcion

            g(a,b) {
                var d,e;
                ....
                ....
                f(b)  ----------------> f(b) { .... return ...}
                .... (1)
                ....
            }

    se introducen en la "pila" los siguientes datos:

            a) Parametros de entrada
            b) Variables locales
            c) DIRECCION DE RETORNO (1)
            d) Valor de retorno

Question 10

¿Qué es la complejidad espacial?

Answer 10

Representa la cantidad de espacio adicional (a los datos de entrada) que necesita el algortimo