Tengo un problema algorítmico
Por ejemplo:
- Si = [1, 3, 4, 1, 3, 6], entonces puede ser [3, 3, 6] o [3, 4, 6] o [4, 3, 6].S
- En = [7, 5, 1, 1, 7, 4], entonces es [7, 5, 7, 4].S
He intentado esta función recursiva.
function(T):
if minimum(T) >= length(T):
return T
else:
return function(T\minimum(T))
¿Hay algún algoritmo no recursivo? (No verifiqué mi algoritmo recursivo, por lo que podría tener algún defecto).
algorithms
optimization
sets
drzbir
fuente
fuente
De mi comentario original: Esto está estrechamente relacionado con una cantidad ubicua en la evaluación de la productividad académica, el índice Hirsh, mejor conocido como el índiceh . En resumen, se define como el número de publicaciones uno tiene de tal manera que cada una de ellas tiene al menos h citas (la mayor h ).h h h
La única forma en que su problema difiere es que le interesaría no solo cuántas publicaciones satisfacen el criterio sino también cuáles son sus recuentos de citas , sino que es una modificación trivial. Los datos ya están allí, el algoritmo original simplemente lo deja caer.
El cálculo generalmente implementado es bastante sencillo y está de acuerdo con la respuesta de Karolis Juodelė .
Actualización: Dependiendo del tamaño y el carácter de sus datos, puede valer la pena explorar métodos que ordenen parcialmente la matriz filtrando los datos por encima y por debajo de un punto crucial (me viene a la mente la clasificación rápida). Luego, dependiendo de si hay muy poco o demasiados, ajuste el pivote y rehaga el subconjunto que lo contiene, y así sucesivamente. No necesita un orden entre elementos superiores a , y ciertamente no entre aquellos inferiores a eso. Entonces, por ejemplo, una vez que encuentre todos los elementos mayores o iguales a h 1 y haya menos de h 1 de ellos, no necesita tocar ese subconjunto nuevamente, solo agréguelo. Esto convierte la recursividad inherente a quicksort en una recursión de cola y, por lo tanto, puede reescribirse como un bucle.h h1 h1
Mi Haskell está un poco oxidado, pero esto debería hacer lo que describí anteriormente y parece funcionar. Espero que se pueda entender hasta cierto punto, me complace proporcionar una explicación más detallada.
La idea es recopilarremaining/2
granted
lo que sabe que definitivamente participará en el resultado, y no ordenarlo más. Sigreater
junto con losx
ajustes, tenemos suerte, de lo contrario, debemos intentar con un subconjunto más pequeño. (El pivotex
es simplemente lo que pasó a ser el primer elemento de la sublista que se considera actualmente). Tenga en cuenta que la ventaja significativa de tomar elementos más grandes uno por uno es que hacemos esto en bloques de tamaño promedio y no es necesario ordenarlos más.Ejemplo:
Tomemos tu set
[1,3,4,1,3,6]
.x = 1
,granted = []
,greater = [3,4,1,3,6]
. Ay, llegamos a un caso patológico cuando el pivote es demasiado pequeño (en realidad tan pequeño quesmaller
está vacío) justo en el primer paso. Afortunadamente nuestro algo está listo para eso. Se descartax
e intenta nuevamente congreater
solo.x = 3
,granted = []
,greater = [4,3,6]
. Juntos, forman una matriz de longitud 4, pero solo tenemos eso limitado desde abajo por 3, así que eso es demasiado. Repitagreater
solo.x = 4
,granted = []
,greater = [6]
. Esto da una matriz de 2 elementos ≥ 4 cada uno, parece que podríamos haber usado algunos más. Mantenga esto y repitasmaller = [3]
.x = 3
,granted = [4,6]
,greater = []
. Esto en conjunto proporciona una matriz de 3 elementos ≥ 3 cada uno, por lo que tenemos nuestra solución[3,4,6]
y podemos regresar. (Tenga en cuenta que la permutación puede variar según el orden de la entrada, pero siempre contendrá los términos más altos posibles, nunca[3,3,6]
o[3,3,4]
para su ejemplo).(Por cierto, tenga en cuenta que la recursión de hecho simplemente colapsó en un ciclo). La complejidad es algo mejor que la clasificación rápida debido a las muchas comparaciones guardadas:
Caso promedio:O(logn) O(n)
Hay algunas comparaciones innecesarias en el código anterior, como calcular
smaller
si lo necesitamos o no, se pueden eliminar fácilmente. (Creo que la evaluación perezosa se encargará de eso).fuente
Su algoritmo no tiene nada de malo y, por supuesto, la mayoría de los algoritmos recursivos se pueden convertir en bucles, aquí hay una versión en bucle de su código recursivo:
fuente
Cualquier algoritmo recursivo puede reescribirse para usar la iteración. Después de todo, una máquina de Turing no sabe nada sobre la recursividad, pero puede implementar cualquier algoritmo. En principio, puede reescribir su función recursiva escribiendo su propio código de manipulación de la pila para recordar los valores de los parámetros de la función y cualquier variable local que pueda tener. En este caso particular, su función es recursiva de cola (una vez que una llamada recursiva regresa, la cosa que la llamó también regresa inmediatamente) por lo que ni siquiera necesita mantener la pila.
fuente
Use un montón mínimo para hacer un montón parcial, ya que no necesita ordenar toda la matriz.
Sigue haciendo estallar elementos con avidez hasta que superes el umbral establecido.
fuente