en tiempo O (n): encuentre el elemento más grande en el conjunto donde la comparación no es transitiva

21

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:

  1. 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)
  2. Se garantiza que cada matriz de entrada tendrá una respuesta
  3. mayor significa que el elemento debe ser mayor que cualquier otro elemento
  4. 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.

James Wierzba
fuente
8
¿No está claro cómo se definiría "el elemento más importante"? Por ejemplo, ¿qué elemento es el mayor si ? ¿Tienes alguna otra regla de comparación? UNA>si,si>do,do>UNA
fade2black
66
No puedo imaginar cómo seleccionaríamos el elemento más grande en un conjunto que no esté al menos parcialmente ordenado. Consulte la definición del elemento mayor y menor. La falta de transitividad descarta el orden parcial.
fade2black
3
@ fade2black ¿Por qué me estás vinculando a otra definición de "grande". Explico explícitamente la definición de grande para el contexto de esta pregunta. Mayor medio, el elemento es mayor que cualquier otro elemento. Ningún elemento es igual. Eso es todo lo que hay que hacer. ¿No está esto claro?
James Wierzba
2
Su último ejemplo con A, B, C, D sería útil para comprender su pregunta si la incluye en su OP.
fade2black
3
Un miembro del equipo del compilador de C # solía hacer esto como una pregunta de entrevista; es relevante porque en C #, el algoritmo de resolución de sobrecarga debe elegir el mejor miembro único de un conjunto dada una relación de "mejora" que suele ser, pero no necesariamente transitiva. (O dé una respuesta adecuada si no hay un miembro tan único; los lazos son posibles). Aunque logré responderlo correctamente, nunca pensé que fuera una pregunta de entrevista particularmente buena, ya que depende de una visión "ajá" para obtener el algoritmo lineal
Eric Lippert

Respuestas:

38

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:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

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).<aijiai>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<<# #unayounayounayo>?unajunayo>unaj# #unayo<norte-1ai<ajo(n2), aún no se vio un máximo, y se puede configurar para que sea uno de los elementos del conjunto.

Ariel
fuente
1
@JamesWierzba (creo) solo quiere decir que un elemento "omitido" es uno que no es mayor que su máximo actual. Considere el algoritmo estándar: verifica cada valor en su lista contra el máximo actual. Has dicho que hay un gran elemento en cada lista. En algún momento, comparará eso con su máximo actual, y dado que es mayor, ese valor se convierte en su nuevo máximo. Debido a que este valor es mayor que todo lo demás en la lista, nunca encontrará un elemento que sea mayor, y su mayor valor no será reemplazado. Después de sus ncomparaciones, su máximo actual tiene que ser la respuesta
Lord Farquaad el
1
Editado para mayor claridad, este algoritmo no asume transitividad. Si le resulta difícil de creer, siga los detalles de la prueba de corrección (suponga con el propósito de contradicción que el valor devuelto no es el máximo, y use la idea del primer párrafo).
Ariel
77
Esto se basa en el supuesto 2 de la pregunta: siempre hay un máximo en la matriz. Si este no fuera el caso, maxsolo 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).
chi
77
Esta respuesta supone que y B > A no pueden sostenerse al mismo tiempo. Por lo que puedo ver, esto no se descarta en la pregunta. A>siB>A
Emil Jeřábek apoya a Monica el
44
@ oconnor0 Eso no sigue. Para un ejemplo concreto, suponga A> B, A> C, B> A y C> B. Entonces A es mayor que cualquier otro elemento del conjunto (y es el único elemento con esta propiedad), pero si los elementos son encontrado en el orden A, B, C, el algoritmo generará C.
Emil Jeřábek apoya a Monica el
24

Como señala Ariel , el algoritmo estándar de búsqueda máxima que figura a continuación:

def find_maximum(a):
    m = a[0]
    for x in a:
        if x > m: m = x
    return m

de hecho funcionará sin modificaciones siempre que:

  • se puede comparar cualquier par de elementos, y
  • se garantiza que la entrada contiene un elemento máximo, es decir, un elemento que es mayor en pares que cualquier otro elemento en la entrada.

(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 > ysiempre es falsa si los elementos xy yson incomparable.)

En particular, su afirmación de que:

[…] Para estar seguro de una respuesta, el elemento debe compararse explícitamente con cualquier otro elemento (porque la comparación no es transitiva).

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:

  1. dado que el ciclo itera sobre todos los elementos de entrada, en alguna iteración xserá el elemento máximo;
  2. Como el elemento máximo es por pares mayor que cualquier otro elemento, se deduce que, al final de esa iteración, mserá el elemento máximo; y
  3. dado que ningún otro elemento puede ser mayor en pares que el elemento máximo, se deduce que mno cambiará en ninguna de las iteraciones posteriores.

Por lo tanto, al final del ciclo, msiempre 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:

def find_maximum_if_any(a):
    # step 1: find the maximum, if one exists
    m = a[0]
    for x in a:
        if x > m: m = x

    # step 2: verify that the element we found is indeed maximal
    for x in a:
        if x > m: return None  # the input contains no maximal element
    return m  # yes, m is a maximal element

(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ón x > men el paso 2 debería reemplazarse x ≠ 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:

  • Si la entrada contiene un elemento máximo, entonces el paso 1 lo encontrará (como se muestra arriba) y el paso 2 lo confirmará.
  • Si la entrada no contiene un elemento máximo, entonces el paso 1 terminará eligiendo algún elemento arbitrario como 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 mla matriz de entrada a, que en realidad podría optimizar el paso 2 solamente para comprobar los elementos que vienen antes mde a, ya que todos los elementos posteriores ya se han comparado con men el paso 1. Sin embargo, esta optimización no cambia el tiempo de complejidad asintótica del algoritmo, que sigue siendo O ( n ).

Ilmari Karonen
fuente
3
De hecho, el OP omite muchos detalles. Por ejemplo, no se dice nada acerca de la reflexividad de la relación, por lo que si no es reflexiva, entonces if x > m:no está definida.
fade2black
4

"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.

n1

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.

Danikov
fuente
1
" Gráfico dirigido acíclico " es el modelo incorrecto: debería ser " torneo ". Los ciclos están permitidos, y es crucial que cada borde exista exactamente en una dirección.
Peter Taylor el
@PeterTaylor tienes toda la razón, solo estaba pensando en las victorias que conducen al elemento 'más grande', las otras victorias son menos relevantes, pero pueden atravesarse en el camino para descubrir lo mejor para que tengas razón de que puedan ' No se descontará
Danikov
3

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á

max = nil
For i=1 to n
   if max is nil then
      max = a[i]
   if max and a[i] are not comparable then
      max = nil
   else if max < a[i] then
      max = a[i]
End

UNA,si,do,re

UNA>si,si>do,do>UNA
re>UNA,re>si,re>do


i=1: max=A
i=2: max=AA>B
i=3: max=CA<C
i=4: max=DD>C

m>aa<mamm<aamam

fade2black
fuente
No creo que else ifse necesite lo primero . No se puede activar si maxes el máximo, y si el máximo aún no se ha encontrado, no importa cuál sea el valor de max.
rici
Sí, ese es el primero. El otro es el segundo :)
rici
¿Quieres decir dejar ifs sin elses? Es solo un hábito: con elses ni siquiera nos comparamos. :)
fade2black
1
¿No sería más simple simplemente inicializar maxa cualquier elemento de la lista y, dentro del ciclo, hacer if 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)?
Ilmari Karonen
1
@badallen el OP supone que siempre existe el elemento más importante. En su ejemplo no hay un elemento más importante.
fade2black
2

A<BB<A

A1...AnAi<Aj

n2

Ai<Ajj

j0Ai<Aj0ijijAi<AjiijAij<Ajj0ij

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.

A<Ann2n

Corinna
fuente
1

A > Bn

O(n)

monstruo de trinquete
fuente