Título: [AYUDA] ¿Cómo hacer este código más eficiente? Publicado por: _TTFH_3500 en 16 Octubre 2018, 00:12 am El siguiente codigo se ejecuta en orden lineal con respecto al tamaño del arreglo A, mi pregunta es cómo hacer dicho codigo más eficiente, digamos O(log n), la idea que tengo es hacer busqueda binaria, es decir, dividir A a la mitad ((i-1) / 2) y buscar en cada mitad.
Pero:
Código
El siguente codigo es O(n^2), lo que si es seguro es que como A está ordenado es posible implementarlo en O(n log n) (La demostración queda a cargo del lector) ¿Alguna idea de por donde empezar? Código
Título: Re: [AYUDA] ¿Cómo hacer este código más eficiente? Publicado por: WHK en 16 Octubre 2018, 00:47 am Creo que lo que buscas es esto:
kPRA0W1kECg Título: Re: [AYUDA] ¿Cómo hacer este código más eficiente? Publicado por: _TTFH_3500 en 16 Octubre 2018, 01:16 am Lo consegui:
Código
Título: Re: [AYUDA] ¿Cómo hacer este código más eficiente? Publicado por: Serapis en 16 Octubre 2018, 02:03 am BuscarIndice no... la función debe llamarse como lo que es una: BusquedaBinaria o dicotomica.
Es posible optimizarla un poco más, si necesitas hacer muchas más búsquedas sobre el mismo array ordenado. Para ello antes de devolver, recuerdas el índice y el valor que acabas de buscar. En la siguiente llamada, al entrar comparas si la entrada es menor mayor o igual que la guardada antes: ---- Si es menor, el espacio de búsqueda se limita a "Min - indicerecordado-1" ---- Si es mayor el espacio de búsqueda se limita a "indicerecordado+1 - max" ---- Si es igual, devuelves el indicerecordado. |