elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Introducción a la Factorización De Semiprimos (RSA)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  [AYUDA] ¿Cómo hacer este código más eficiente?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [AYUDA] ¿Cómo hacer este código más eficiente?  (Leído 691 veces)
_TTFH_3500

Desconectado Desconectado

Mensajes: 119



Ver Perfil
[AYUDA] ¿Cómo hacer este código más eficiente?
« 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:
  • Si encuentro un i > 0 en la primera mitad deberia buscar en la segunda. (podria existir un i mayor)
  • Si no encuentro un i > 0 en la segunda mitad debería buscar en la primera si no lo hice antes. (ya que podria existir un i > 0)
Por lo que sigue siendo O(n) en el peor caso, quiza no sea posible implementarlo en O(log n)

Código
  1. /* A[1..n] esta ordenado de menor a mayor
  2.  * Devuelve el mayor indice i' menor o igual a i tal que A[i'] <= c
  3.  * o cero si no se encuentra. Cota superior asintotica: O(n)
  4.  */
  5. void buscarIndice(const uint* A, uint &i, const uint c) {
  6. while (i > 0 && A[i] > c)
  7. i--;
  8. }
  9.  

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
  1. for (uint j = 1; j <= n; j++) {
  2. uint i = j; // No es ortodoxo modificar j
  3. buscarIndice(A, i, c);
  4. hacerAlgoUtilCon(i);
  5. }


En línea

WHK
CoAdmin
***
Desconectado Desconectado

Mensajes: 6.404


The Hacktivism is not a crime


Ver Perfil WWW
Re: [AYUDA] ¿Cómo hacer este código más eficiente?
« Respuesta #1 en: 16 Octubre 2018, 00:47 am »

Creo que lo que buscas es esto:



En línea

Telegram: @WHK102 - Semáforo Epidemiologico Chile
_TTFH_3500

Desconectado Desconectado

Mensajes: 119



Ver Perfil
Re: [AYUDA] ¿Cómo hacer este código más eficiente?
« Respuesta #2 en: 16 Octubre 2018, 01:16 am »

Lo consegui:
Código
  1. uint buscarIndice(const uint* A, uint i, uint c) {
  2. uint l = 1, r = i;
  3. while (l <= r) {
  4. uint m = (l + r) / 2;
  5. if (A[m - 1] <= c) {
  6. if (A[m] <= c)
  7. l = m + 1;
  8. else
  9. return m;
  10. } else
  11. r = m - 1;
  12. }
  13. return 0;
  14. }
  15.  
En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 2.465


Ver Perfil
Re: [AYUDA] ¿Cómo hacer este código más eficiente?
« Respuesta #3 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.
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines