Edad: 38
Registrado: 29 Oct 2005
Mensajes: 2725
Ubicación: Rivadavia y Puan
Carrera: Civil
Supongo que hay dos formas.
Partiendo de un arreglo que contenga los números en el orden de ingreso (y sabiendo su dimensión)
* La trivial
Iterar posición por posición y hacer la cuentita de cuantos cumplen cada condición...
* La compleja y eficiente °°
Ordenar el arreglo (con un método piola).
Buscar por algún método log N la posición del item que arranca a cumplirlo y obtener el total por mera álgebra. (doble borde, doble búsqueda pero idem álgebra)
Tal vez exista una manera eficiente de ordenar un arreglo a medida que ingresan los datos. El problema de ordenar un arreglo de manera eficiente está super desarrollado en cualquier libro (quickshort, burbuja,..) El problema de hacer una búsqueda inteligente es trivial y consiste en dividir el intervalo en mitades y ver de que lado te queda el valor buscado hasta converger en un "punto".
**********
Por lo que estudiás, te recomiendo hacer la segunda, máxime que no es fecha de exámenes.
La trivial, va a tener complejidad donde n es la cantidad de elementos y c la cantidad de condiciones. O sea, va a tener tiempo lineal.
La "eficiente", sólo por el hecho de ordenar, genéricamente debería tener un orden al menos . Salvo que haya particularidades de tu conjunto de datos que te permita obtener un mejor tiempo del orden (que nunca va a ser menos que lineal); siempre va a ser peor que la trivial. Como mucho (restricciones sobre el conjunto de entrada), vas a poder hacer que sean iguales.
Una no tan trivial sería armar una secuencia en que los valores que fueron rechazados en el primer test sean el input del segundo (siempre y cuando las condiciones lleven a conjuntos disjuntos, como en el ejemplo que diste).
Una no tan trivial sería armar una secuencia en que los valores que fueron rechazados en el primer test sean el input del segundo (siempre y cuando las condiciones lleven a conjuntos disjuntos, como en el ejemplo que diste).
En implementación, eso se marca usando un else antes del if; es optimización pero menor, te da un speedup pero no te cambia el orden.
Edad: 38
Registrado: 29 Oct 2005
Mensajes: 2725
Ubicación: Rivadavia y Puan
Carrera: Civil
¿si el "log" n es menor que el número de restricciones? Las restricciones pueden ser en realidad un pedido a la base de datos.
Cita:
Entiendo perfectamente tu punto pero supongo que depende de la relación entre el tamaño del arreglo y la cantidad de búsquedas que se haga. Tiré una solución "rica".
De hecho vos si sos profesional y docente. ¿Como se gestiona esto en una base de datos mas allá del "lenguaje"?
¿si el "log" n es menor que el número de restricciones? Las restricciones pueden ser en realidad un pedido a la base de datos.
Entiendo perfectamente tu punto pero supongo que depende de la relación entre el tamaño del arreglo y la cantidad de búsquedas que se haga. Tiré una solución "rica".
No sé si entiendo bien la pregunta, pero intento respondértela.
En el problema que plantea él, la idea es tener un par de búsquedas fijas y tener un conjunto variable de datos de entrada. Entonces, el tiempo de búsqueda no puede disociarse del tiempo de organización de los datos.
En el algoritmo que planteaste como trivial, por cada dato, hacés las restricciones, por lo que las operaciones que hiciste quedan función de los datos y las restricciones.
En la otra solución tenés dos partes. Una es ordenar, lo cual tiene un tiempo como mínimo n log n (no importa mucho el valor de n, para n > e, eso da más que lineal); y una vez que se hizo ese pre-procesamiento, cada búsqueda te va a llevar algo de orden log n con búsqueda binaria.
Entonces, la solución completa sería: n log n + c log n, donde c son otra vez, el número de restricciones. Si c < n, como cota puede dejarse n log n, y si c > n, como cota puede dejarse c log n. Como mínimo, entonces, el tiempo total va a ser n log n.
Si se ponen las dos curvas en función de c, se va a ver que las dos se cruzan. Para c chico, nc va a ser menor que n log n; para c grande, c log n va a ser menor que n c. Entonces, sí, si el caso fuera al revés, los datos están fijos y lo que uno va a variar son las consultas; puede convenir hacer el preprocesamiento.
Ignium escribió:
De hecho vos si sos profesional y docente. ¿Como se gestiona esto en una base de datos mas allá del "lenguaje"?
Ahí lo gestiona la base de datos; y ya es imposición que haya una carga previa en memoria de todos los valores.
Si creas una tabla indexada por el valor, va a crearse un índice donde buscar debería darte un orden logarítmico.
Un: "SELECT COUNT(*) FROM datos WHERE valor < 30;" dependiendo de la implementación del motor, podría partir de un mínimo de tiempo logarítimico hasta un máximo de lineal. Pero depende mucho de la implementación... por ejemplo, dudo mucho que eso en Access vaya a darte orden logarítmico.
Pero les comento que estoy trabajando con diagramas de flujo, y no comprendo todo eso de los logaritmos.
Les explico lo que a mi se me ocurre:
Este sería el pseudocódigo:
Inicio
1.- Declaración de variables: n1, n2, n3, n4, n5, n6, n7, n8, n9, n10
2.- Escribir el mensaje: Teclea el 1er. número:
3.- Almacenar el numero en la variable n1
4.- Escribir el mensaje: Teclea el 2do. número:
5.- Almacenar el numero en la variable n2
.
.
.
Escribir el mensaje: Teclea el 10mo. número:
Almacenar el numero en la variable n10
ya de ahi no se como seguir...
Para comparar y ver en que rango esta un número se me ocurre esto:
Si n1 > 100
Entonces mayor1 = n1 (Almaceno el valor en una variable llamada mayor1)
Si n2 > 100
Entonces mayor2 = n2 (Almaceno el valor en una variable llamada mayor2)
.
.
Así sucesivamente con los demás.
Después tendria que volverlos a comparar pero ahora así:
Si n1 >= 30 AND n1 <50>= 30 AND n1 <=50
Entonces rango2 = n2
.
.
Así sucesivamente con los demás.
Y después tendría que comprararlos así:
Si n1 < 30
Entonces menor1 = n1
Si n2 < 30
Entonces menor2 = n2
.
.
Así sucesivamente con los demás.
Pero no se como implementarlo ya siguiendo este proceso tendria que agregar todas las comparaciones varias veces, es dedir todas las comparaciones anteriores dentro de cada comparación dando una cantidad gigantezca de comparaciones y para imprimirlos lo que haria dentro de camino del ciclo SI ( if ) es imprimir las variables de la siguiente forma:
Mayores a 100 estan: mayor1, mayor2, mayor3, ... , mayor10
Entre 30 y 50 estan: rango1, rango2, rango3, ... , rango 10
Menores a 30 estan: menor1, menor2, menor3, ... , menor10
Aqui supongo que no importa que se impriman todas las variables ya que al declararlas no se les asigno un valor y por lo tanto no tendrán nada, excepto a las que se les haya asignado un valor de los leidos despues de cumplirse una condición.
Yo usaría 4 vectores, en uno almacenas todos los números y después con un ciclo pasas por cada número y verificas las condiciones, cuando cumple una guardas ese número en el vector correspondiente a esa condición y al final imprimis el contenido de cada vector...
Y cuando tenga los números en un arreglo como lo recorro?, es decir como quedaría el ciclo para pasar por cada número? y las condiciones todas se verifican dentro del mismo ciclo?
Asi vas a estar imprimiendo los 10 espacios de los 3 vectores, de los cuales varios van a estar vacios.
Quizas te conviene armar tres contadores dentro del ciclo for para almacenar la cantidad de números que cumple cada una de las condiciones y después saber cuantos exactamente imprimir (con otros 3 ciclos for).
Ver tema siguiente Ver tema anterior Podés publicar nuevos temas en este foro No podés responder a temas en este foro No podés editar tus mensajes en este foro No podés borrar tus mensajes en este foro No podés votar en encuestas en este foro No Podéspostear archivos en este foro No Podés bajar archivos de este foro
Todas las horas son ART, ARST (GMT - 3, GMT - 2 Horas)
Protected by CBACK CrackerTracker 365 Attacks blocked.
![[tex]\mathcal O(nc)[/tex]](images/latex/e9139e8528daf35365776df70040fbc3fa72d809_0.png "[tex]\mathcal O(nc)[/tex]")
donde n es la cantidad de elementos y c la cantidad de condiciones. O sea, va a tener tiempo lineal.
![[tex]\mathcal O(n \log n)[/tex]](images/latex/66ca11f3a1b2668aced0c41adc9a718175e75e7a_0.png "[tex]\mathcal O(n \log n)[/tex]")
. Salvo que haya particularidades de tu conjunto de datos que te permita obtener un mejor tiempo del orden (que nunca va a ser menos que lineal); siempre va a ser peor que la trivial. Como mucho (restricciones sobre el conjunto de entrada), vas a poder hacer que sean iguales.
![[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]](images/latex/d678cf273c99d2546c259db3422b3d968b184721_0.png "[tex] ${. \ \ \ \ \ \ \ \ \ .}$ [/tex]")
![[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]](images/latex/1e6580e1ed9e054ddefd65c0551c670c44f57f38_0.png "[tex] ${\Large Usá \LaTeX, no seas foro...}$ [/tex]")
