El título establece la pregunta.
Tenemos como entradas una lista de elementos que podemos comparar (determinar cuál es el mejor ). Ningún elemento puede ser igual.
Puntos clave:
- La comparación no es transitiva (piense en piedra, papel o tijera): esto puede ser cierto: A> B, B> C, C> A (tenga en cuenta que esto no es una entrada válida ya que no hay una respuesta válida aquí, solo estoy describiendo qué " comparación no transitiva "significa)
- Se garantiza que cada matriz de entrada tendrá una respuesta
- mayor significa que el elemento debe ser mayor que cualquier otro elemento
- La propiedad inversa se mantiene, es decir, A> B implica que B <A
Ejemplo:
Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D
No puedo encontrar una manera de hacer esto en O (n) tiempo, mi mejor solución es O (n ^ 2).
Me atoro en cada enfoque debido al hecho de que para estar seguro de una respuesta, el elemento necesita ser comparado explícitamente con cualquier otro elemento, para demostrar que es la respuesta (porque la comparación no es transitiva).
Esto descarta el uso de un montón, clasificación, etc.
algorithms
time-complexity
sets
transitivity
James Wierzba
fuente
fuente
Respuestas:
El algoritmo estándar para encontrar un máximo todavía funciona. Comience con y los elementos, si ve un valor mayor, actualice el máximo para que sea ese valor. La razón por la que esto funciona es que cada elemento que omitió es más pequeño que al menos un elemento y, por lo tanto, no puede ser el máximo.a1
Para ser claros, por "algoritmo estándar" me refiero a lo siguiente:
Para completar, discutiré aquí las cuestiones planteadas en los comentarios. La configuración en la discusión anterior es encontrar un máximo relativo a una relación antisimétrica , donde es un máximo si para todo tenemos . El algoritmo anterior funciona bajo el supuesto de que existe un máximo, sin embargo, si esto no se conoce, se puede usar para verificar la existencia de un máximo (verifique si el elemento devuelto es realmente mayor que todos los demás elementos, esto se menciona en el comentario de Chi y en la respuesta de Ilmari Karonen).< ai j≠i ai>aj
Si no es necesariamente antisimétrico, entonces el algoritmo anterior falla (como Emil mencionó en los comentarios). Si es una relación arbitraria (es decir, estamos relajando tanto la transitividad como la antisimetría), entonces no es difícil demostrar que no es posible encontrar un máximo en el tiempo lineal. Denotamos por la cantidad de veces que participó en una consulta, definimos una relación de confrontación de manera que el máximo no se pueda revelar sin suficientes consultas. Dada la consulta , responda si y contrario. Si el número de consultas es< < # ayo unayo unayo> ? unaj unayo> aj # ayo< n - 1 ai<aj o(n2) , aún no se vio un máximo, y se puede configurar para que sea uno de los elementos del conjunto.
fuente
n
comparaciones, su máximo actual tiene que ser la respuestamax
solo podría ser el máximo de una submatriz. Aún así, incluso sin el supuesto 2, uno puede encontrar un máximo tentativo y luego verificarlo en toda la matriz utilizando un segundo escaneo, dentro del límite O (n).Como señala Ariel , el algoritmo estándar de búsqueda máxima que figura a continuación:
de hecho funcionará sin modificaciones siempre que:
(La primera suposición anterior en realidad puede estar relajado, incluso sin tener que modificar el algoritmo, el tiempo que se supone que el elemento de máxima es comparable con cualquier otro elemento y que
x > y
siempre es falsa si los elementosx
yy
son incomparable.)En particular, su afirmación de que:
no es cierto bajo los supuestos dados anteriormente. De hecho, para demostrar que el algoritmo anterior siempre encontrará el elemento máximo, es suficiente observar que:
x
será el elemento máximo;m
será el elemento máximo; ym
no cambiará en ninguna de las iteraciones posteriores.Por lo tanto, al final del ciclo,
m
siempre será el elemento máximo, si la entrada contiene uno.PD. Si la entrada no siempre contiene necesariamente un elemento máximo, entonces verificar ese hecho requerirá probar la respuesta del candidato contra cualquier otro elemento para verificar que es realmente máxima. Sin embargo, todavía podemos hacer eso en O ( n ) tiempo después de ejecutar el algoritmo de búsqueda máxima anterior:
(Asumo aquí que la relación
>
es irreflexiva, es decir, ningún elemento puede ser mayor que sí mismo. Si ese no es necesariamente el caso, la comparaciónx > m
en el paso 2 debería reemplazarsex ≠ m and x > m
, donde≠
denota la comparación de identidad. O simplemente podríamos aplicar la optimización anotado abajo.)Para probar la exactitud de esta variación del algoritmo, considere los dos casos posibles:
m
. No importa qué elemento sea, ya que en cualquier caso no será máximo, y por lo tanto, el paso 2 lo detectará y volveráNone
.Si almacenamos el índice de
m
la matriz de entradaa
, que en realidad podría optimizar el paso 2 solamente para comprobar los elementos que vienen antesm
dea
, ya que todos los elementos posteriores ya se han comparado conm
en el paso 1. Sin embargo, esta optimización no cambia el tiempo de complejidad asintótica del algoritmo, que sigue siendo O ( n ).fuente
if x > m:
no está definida."mayor significa que el elemento debe ser mayor que cualquier otro elemento" es una gran pista sobre cómo hacer esto en .O(n)
Si revisa los elementos de comparación de su lista, cualquier elemento que "pierda" una comparación puede descartarse inmediatamente ya que, para ser el más grande, debe ser mayor que TODOS los demás elementos, por lo que la pérdida individual lo descalifica.
Esta solución está habilitada por una sutileza: "Ningún elemento puede ser igual" combinado con el hecho de que siempre habrá un elemento mayor. Si mapeamos las relaciones de victorias como un gráfico dirigido, está claro que podemos alcanzar el elemento más grande simplemente siguiendo las victorias.
fuente
Supongo que la relación antisimétrica para al menos un solo elemento (que garantiza la existencia del elemento más grande), de lo contrario, la tarea es imposible. Si todos los elementos en el conjunto finito son comparables, entonces el procedimiento habitual de búsqueda máxima funciona.
Si algunos elementos no son comparables, el siguiente procedimiento funcionará
fuente
else if
se necesite lo primero . No se puede activar simax
es el máximo, y si el máximo aún no se ha encontrado, no importa cuál sea el valor demax
.if
s sinelse
s? Es solo un hábito: conelse
s ni siquiera nos comparamos. :)max
a cualquier elemento de la lista y, dentro del ciclo, hacerif max and a[i] are comparable and max < a[i] then max = a[i]
(donde la primera parte de la condición podría omitirse si asumimos que intentar comparar dos elementos incomparables siempre produce falso)?Espero que esto sea algo comprensible. Siéntase libre de preguntar en comentarios o editar.
La idea básica es que no puede recopilar ninguna información sobre los elementos restantes de los que ya conoce si permite una relación completamente arbitraria.
fuente
A > B
fuente