A surpassing problem

propuesto por josejuan

JAlonso tuiteó un libro que contiene una serie de problemas. En él se presenta un problema que se resuelve con coste O(n log n). El desafío consiste en encontrar una solución con coste O(n) y ver porqué en la práctica NO ES más eficiente.

Enunciado
JAlonso tuiteó un libro (Texto del enlace) que contiene una serie de problemas. En él se presenta un problema que se resuelve con coste O(n log n). El desafío consiste en encontrar una solución con coste O(n) y ver porqué en la práctica NO ES más eficiente que la del libro (obviamente haciendo crecer 'n' llegará un momento que será mejor la lineal) y mostrar en que condiciones sería más eficiente que el mostrado en el libro.

Como el libro no concreta exactamente los requisitos del problema (de hecho lo modifican ligeramente sobre la marcha), lo haré yo haciendo una sutilísima pero transcendete aclaración.

El enunciado es el siguiente:
  • Sea "C" un conjunto finito de elementos ordenados.
  • Dada una cadena "S" de elementos de "C", se dice que "x" es "surpasser" de "y", si es "y < x" y además, "y" está delante de "x" dentro de la cadena "S".
  • Se llama "surpasser count" de un elemento "x" en la cadena "S" al número de "surpasser" que posee dentro de esa cadena.
  • El desafío consiste en encontrar un algoritmo que calcule el máximo "surpasser count" dada una cadena "S" de elementos de un conjunto "C". Dicho algoritmo tiene que ser O(n).

Por ejemplo:
  • Sea "C" el conjunto ordenado de las letras mayúsculas "ABCDE...XYZ".
  • Sea "S" la cadena "GENERATING".
  • Entonces, los "surpassing count" son respectivamente "5625140100".
  • Entonces, el máximo "surpassing count" es el "6".

Explicación del ejemplo:
  • La primera letra "G" tiene a su derecha 5 letras mayores que ella.
  • La segunda letra "E" tiene a su derecha 6 letras mayores que ella.
  • La tercera letra "N" tiene a su derecha 2 letras mayores que ella.
  • La cuarta letra "E" tiene a su derecha 5 letras mayores que ella.
  • ...
  • El máximo de los anteriores es 6.

Ver todo el enunciado

Preguntas sobre el desafío
  • ¿A que te refieres con n? ¿a la longitud de S o de C? Si es la de S se podria conseguir O(n*m) iterando una vez sobre S y en cada paso iterando sobre los elementos de C siendo m la longitud de C. No se si ese es el objetivo del desafio o el "truco" para conseguir O(n) aunque "en la practica" sea mas costoso

    Se dice que el conjunto es finito, por tanto "C" no crece.
    "S" es el dato de entrada y cuya longitud puede ponerse en correspondencia con el coste.

    Como bien dices, la solución en la que estaba pensando cuando escribí el desafío es la que comentas (falta describir adecuadamente cuando es mejor O(n) que O(n log n)), sin embargo, creo estar seguro de haber encontrado una versión O(n) que mejora O(n log n) salvo quizás valores pequeños de 'n' (en valores pequeños de 'n' las constantes multiplicativas tienen mucho peso).

    Muy bien apuntado el O(n m), de hecho, es habitual incluir en el coste el tamaño del alfabeto pues ahí está la gracia (en la relevantísima constante multiplicativa) y como dices, el "truco".

    Ya que lo tienes, ¿sabrías encontrar el algoritmo O(n) eficiente? (con constante pequeña).

Plantea tu pregunta

6 Soluciones

Dar mi solución

0votos
A surpassing problem en JavaScript
por

josejuan

hace 6 años

El coste en el peor caso es O(n + min(S, n)^2); si se asume S < n entonces el coste es O(n + S^2), la mejora consiste en que los datos de entrada sólo se recorren una única vez. La contrapartida es que para valores grandes de S tendríamos coste cuadrático (aunque puede mejorarse). Por ejemplo, para tamaños de S=1024 usaríamos y moveríamos 1M de datos, lo que es un coste muy pequeño si n es grande.

0votos
A surpassing problem en Java
por

Eduardo

hace 6 años

Esta solución asume que el orden en C es natural, en otro caso habría que ordenar respecto a tal orden. Solo es necesario recorrer S una vez. Nota: me confundí en el método de búsqueda escogido en la anterior solución (no aprovechaba que la lista esté ordenada).

Dar mi solución