Quiero escribir un programa para encontrar el n-ésimo elemento más pequeño sin utilizar ninguna técnica de clasificación ...¿Busca el n-ésimo elemento más pequeño en la matriz sin ordenar?
¿Podemos hacerlo recursivamente, dividir y conquistar el estilo como ordenar rápidamente?
Si no, ¿cómo?
Puede encontrar información sobre este problema aquí: Selection algorithm.
Se pueden utilizar dos pilas de esta manera para ubicar el n-ésimo número más pequeño en una sola pasada.
por lo general de acuerdo al análisis de optimización Noldorins'.
Esta solución de pila se dirige hacia un esquema simple que funcionará (con un movimiento de datos relativamente mayor: en las dos pilas). El esquema de montón reduce la búsqueda para el N-ésimo número más pequeño a un cruce de árbol (log m).
Si su objetivo es una solución óptima (por ejemplo, para un gran conjunto de números o tal vez para una asignación de programación, donde la optimización y la demostración de la misma son críticas) debe utilizar la técnica de pila.
La solución de pila se puede comprimir en requisitos de espacio implementando las dos pilas dentro del mismo espacio de elementos K (donde K es el tamaño de su conjunto de datos). Por lo tanto, la desventaja es solo el movimiento extra de la pila a medida que se inserta.
esta tarea es bastante posible completar dentro de más o menos O(n) tiempo (n siendo la longitud de la lista) mediante el uso de un heap structure (específicamente, un priority queue basado en un Fibonacci heap), que da O(1) tiempo de inserción y O(log n) tiempo de eliminación).
Considere la tarea de recuperar el m-ésimo elemento más pequeño de la lista. Simplemente recorriendo la lista y agregando cada elemento a la cola de prioridad (del tamaño m), puede crear efectivamente una cola de cada uno de los elementos en la lista en el tiempo O(n) (o posiblemente menos usando algunas optimizaciones, aunque no estoy seguro que esto es extremadamente útil).Entonces, es una cuestión simple de eliminar el elemento con la prioridad más baja en la cola (la prioridad más alta es el elemento más pequeño), que solo toma O(log m) tiempo en total, y ya ha terminado.
Así que en general, la complejidad temporal del algoritmo sería O(n + log n), pero desde log n << n (es decir n crece mucho más rápido que log n), esto reduce simplemente a O(n). No creo que pueda obtener nada significativamente más eficiente que esto en el caso general.
(1) ¿cómo se obtiene una cola de prioridad "de tamaño m"? ¿Sabe de alguna manera cuál es el objeto más grande que tirar cuando agregas otro? (2) suponiendo que tengas una estructura así, todavía no veo cómo obtuviste O (log m). ¿No deberías necesitar multiplicar por m porque tienes que eliminar m cosas para llegar al punto más pequeño? – newacct
@newacct: En esencia tiene razón sobre el punto 1. Puede limitar el tamaño de la cola de prioridad hasta cierto punto (verificando el artículo máximo después de que se llena, por ejemplo), pero no al tamaño m. En cuanto al punto 2, eso no es verdad. De hecho, puede recuperar el elemento más grande en el tiempo de registro n (en lugar de m, con la corrección del punto 1): la cola de prioridad permite el acceso a los elementos máximo o mínimo en el tiempo de registro n; son solo los intermedios los que tardan más en llegar. – Noldorin
¿Por qué mi solución anterior no es la mejor? .. Quiero saber cuál es el problema con mi solución – Learner
Lo que te refieres es el Algoritmo de selección, como se indicó anteriormente. Específicamente, su referencia a quicksort sugiere que está pensando en el partition based selection.
Así es como funciona:
Este algoritmo también es útil para encontrar una lista ordenada de los elementos m más altos ... simplemente seleccione el elemento m más grande, y ordene la lista de arriba. O bien, para un algoritmo que sea un poco más rápido, realice el algoritmo Quicksort, pero decida no recurrir en regiones que no se solapen con la región para la que desea encontrar los valores ordenados.
Lo mejor de esto es que normalmente se ejecuta en el tiempo O (n). La primera vez, ve la lista completa. En la primera recursión, ve aproximadamente la mitad, luego un cuarto, etc. Por lo tanto, mira alrededor de 2n elementos, por lo tanto, se ejecuta en O (n) tiempo. Desafortunadamente, como en el servicio rápido, si elige constantemente un pivote incorrecto, se ejecutará en O (n) vez.
Puede usar el montón binario, si no desea utilizar el montón de fibonacci.
Algo:
Contruct el montón binario min de la matriz de esta operación tomará tiempo O (n).
Dado que este es un montón binario mínimo, el elemento en la raíz es el valor mínimo.
Así que sigue eliminando el elemento frm root, hasta que obtengas tu mínimo valor. o (1) operación
Asegúrese de que después de cada extracción vuelva a almacenar la operación de pila kO (logn).
Entonces, ejecutar tiempo aquí es O (klogn) + O (n) ............ por lo que es O (klogn) ...
Here is the Ans to find Kth smallest element from an array:
#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int Nthmin=0,j=0,i;
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall);
int main()
{
int size;
cout<<"Enter Size of array\n";
cin>>size;
int *arr=(int*)malloc(sizeof(int)*size);
cout<<"\nEnter array elements\n";
for(i=0;i<size;i++)
cin>>*(arr+i);
cout<<"\n";
for(i=0;i<size;i++)
cout<<*(arr+i)<<" ";
cout<<"\n";
int n=sizeof(arr)/sizeof(int);
int result=GetNthSmall(arr,size,3);
printf("Result = %d",result);
getch();
return 0;
}
int GetNthSmall(int numbers[],int NoOfElements,int Nthsmall)
{
int min=numbers[0];
while(j<Nthsmall)
{
Nthmin=numbers[0];
for(i=1;i<NoOfElements;i++)
{
if(j==0)
{
if(numbers[i]<min)
{
min=numbers[i];
}
Nthmin=min;
}
else
{
if(numbers[i]<Nthmin && numbers[i]>min)
Nthmin=numbers[i];
}
}
min=Nthmin;
j++;
}
return Nthmin;
}
Sonidos como este algoritmo es en general el tiempo O (nm), siendo n la longitud de la lista, m como en el m-ésimo elemento más pequeño. – Noldorin
Esto es solo un tipo de inserción. – newacct
Sí, esto solo está ordenando usando la pila – Learner