En primer lugar, deberíamos mirar la versión recursiva del tipo de selección.
El siguiente es un código abstracto tipo java para la selección recursiva:
Algoritmo: Selección-Clasificación-rec
Entrada: matriz sin clasificar con longitud n
Salida: matriz ordenada
Procedimiento:
SelectionSort (arr [])
Devuelve Sel-sort-rec (arr, 0, arr.length-1)
Sel-sort-rec (arr [], int actual, int final)
if (actual == final)
Regreso arr
más
min = arr [actual]
para (int i = actual + 1, i <= fin, i ++)
if (arr [min]> arr [i])
min = i
intercambio (arr, actual, min)
Sel-sort-rec (arr, ++ actual, final)
- ¿Qué son los algoritmos y la estructura de datos y cómo puedo comenzar con ellos?
- ¿Cuál es el algoritmo de aprendizaje automático más útil para Google?
- ¿Cómo reconocen los programas el nombre usando el procesamiento del lenguaje natural?
- ¿Los desarrolladores de Google realmente usan conceptos como la notación O grande para determinar el tiempo de ejecución de un algoritmo en un proceso de codificación diario?
- En el algoritmo KNN, ¿por qué el pequeño valor de k conduce a una pequeña tasa de error?
Claramente, estamos realizando operaciones O (final – actual) en cada llamada recursiva. También estamos realizando N llamadas recursivas.
¡Aceptemos que si N = 1, entonces solo habrá una operación, la declaración de devolución!
Si N = 2, entonces tendremos n operaciones “de la construcción else” + una llamada recursiva con un parámetro (n-1)
En base a eso, consigamos la fórmula recursiva, representaremos llamadas recursivas como una función F (n):
Si n = 1, F (n) = 1
de lo contrario F (n) = F (n-1) + n.
Como estamos interesados en el número de comparaciones elemet, podemos ignorar aquellas operaciones realizadas por la función de intercambio que es de tiempo constante.
Al resolver esta recurrencia, se nos ocurrirá la misma ecuación obtenida por la versión iterativa del tipo Selección que es [matemática] \ sum_ {i = 0} ^ {n-1} = \ frac {n (n-1) } {2} [/ matemáticas].
Tenga en cuenta que hay algunos algoritmos en los que su versión recursiva no se comporta de la misma manera que su versión iterativa . El tipo de fusión es un buen ejemplo para mirar.
