in O (n) time: Encontre o maior elemento do conjunto onde a comparação não é transitiva

21

O título indica a pergunta.

Temos como entradas uma lista de elementos que podemos comparar (determinar qual é o melhor ). Nenhum elemento pode ser igual.

Pontos chave:

  1. A comparação não é transitiva (pense em uma tesoura de papel de pedra): isso pode ser verdade: A> B, B> C, C> A (observe que não é uma entrada válida, pois não há resposta válida aqui, apenas descrevo o que " comparação não transitiva "significa)
  2. Cada matriz de entrada é garantida para ter uma resposta
  3. maior significa que o elemento deve ser maior que qualquer outro elemento
  4. A propriedade inversa mantém ou seja, A> B implica que B <A

Exemplo:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

Não consigo descobrir uma maneira de fazer isso em O (n) tempo, minha melhor solução é O (n ^ 2).

Fico presa em todas as abordagens devido ao fato de que, para ter certeza de uma resposta, o elemento precisa ser explicitamente comparado a qualquer outro elemento, para provar que é realmente a resposta (porque a comparação não é transitiva).

Isso exclui o uso de uma pilha, classificação etc.

James Wierzba
fonte
8
Não está claro como "o maior elemento" seria definido? Por exemplo, qual elemento é o maior se ? Você tem outras regras de comparação? UMA>B,B>C,C>UMA
Fade2black 20/11
6
Não consigo imaginar como selecionaríamos o maior elemento em um conjunto que não é pelo menos parcialmente ordenado. Por favor, veja a definição do maior e menor elemento. A falta de transitividade exclui a ordem parcial.
Fade2black 20/11
3
@ fade2black Por que você está me vinculando a outra definição de "melhor". Estou declarando explicitamente a definição de maior para o contexto desta questão. Maiores meios, o elemento é maior que qualquer outro elemento. Nenhum elemento é igual. Isso é tudo o que existe. Isso não está claro?
James Wierzba
2
Seu último exemplo com A, B, C, D seria útil para você entender se você o incluiu no seu OP.
Fade2black
3
Um membro da equipe do compilador C # costumava fazer isso como uma pergunta de entrevista; é relevante porque, em C #, o algoritmo de resolução de sobrecarga deve escolher o melhor membro único de um conjunto, dada uma relação de "sem firmeza" que geralmente é, mas não necessariamente, transitiva. (Ou dê uma resposta adequada se não houver um membro tão único e único; são possíveis laços.) Embora eu tenha conseguido responder corretamente, nunca pensei que fosse uma pergunta de entrevista particularmente boa, pois se baseia em um insight "aha" para obter as informações necessárias. algoritmo linear.
precisa

Respostas:

38

O algoritmo padrão para encontrar um máximo ainda funciona. Comece com e passar por cima dos elementos, se você vê um valor maior, atualizar o máximo para ser esse valor. A razão pela qual isso funciona é que cada elemento que você pulou é menor que pelo menos um elemento e, portanto, não pode ser o máximo.a1

Para ser claro, com o "algoritmo padrão" quero dizer o seguinte:

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

Para ser completo, discutirei aqui as questões levantadas nos comentários. A configuração na discussão acima é encontrar um máximo em relação a uma relação anti-simétrica , em que< é um máximo se para todo j i temos um i > um j . O algoritmo acima funciona sob a suposição de que existe um máximo, no entanto, se isso não for conhecido, pode-se usá-lo para verificar a existência de um máximo (verifique se o elemento retornado é realmente maior que todos os outros elementos, isso é mencionado no comentário de Chi e na resposta de Ilmari Karonen).umaEujEuumaEu>umaj

Se não for necessariamente anti-simétrico, o algoritmo acima falhará (como Emil mencionado nos comentários). Se < é uma relação arbitrária (isto é, estamos relaxando a transitividade e a antimetria), não é difícil mostrar que não é possível encontrar um máximo no tempo linear. Denote por # a i o número de vezes que um i participou de uma consulta, nós definimos uma relação adversarial de uma forma que o valor máximo não pode ser revelado sem consultas suficientes. Dada a consulta a i > ? a j , responda a i > a j se # a i<<#umaEuumaEuumaEu>?umajumaEu>umaj e a i < a j caso contrário. Se o número de consultas for o ( n 2 ) , um máximo ainda não foi visto e pode ser definido como um dos elementos do conjunto.#ai<n1ai<ajo(n2)

Ariel
fonte
1
@ JamesWierzba (eu acho), ele apenas quer dizer que um elemento "ignorado" não é maior que o seu máximo atual. Considere o algoritmo padrão: você verifica cada valor na sua lista com o máximo atual. Você disse que há um grande elemento em cada lista. Em algum momento, você comparará isso com o seu máximo atual e, como é maior, esse valor se tornará o seu novo máximo. Como esse valor é maior que tudo na lista, você nunca encontrará um elemento que seja maior e seu maior valor não será substituído. Depois de suas ncomparações, seu máximo atual tem que ser a resposta
Lord Farquaad
1
Editado para maior clareza, esse algoritmo não assume transitividade. Se você achar isso difícil de acreditar, siga os detalhes da prova de correção (suponha, com a finalidade de contradição, que o valor retornado não seja o máximo, e use a ideia do primeiro parágrafo).
Ariel #
7
Isso se baseia na suposição 2 da pergunta: sempre há um máximo no array. Se não fosse esse o caso, maxsó poderia ser o máximo de um subarray. Mesmo assim, mesmo sem a suposição 2, é possível encontrar um máximo provisório e depois verificá-lo em toda a matriz usando uma segunda varredura, dentro do limite O (n).
21417 chi
7
Esta resposta assume que e B > A não podem ser mantidos ao mesmo tempo. Tanto quanto posso ver, isso não está descartado na questão. A>BB>A
Emil Jeřábek apoia Monica
4
@ oconnor0 Isso não se segue. Para um exemplo concreto, assuma A> B, A> C, B> A e C> B. Então A é maior que qualquer outro elemento do conjunto (e é o único elemento com essa propriedade), mas se os elementos forem encontrado na ordem A, B, C, o algoritmo produzirá C.
Emil Jeřábek suporta Monica
24

Como observa Ariel , o algoritmo padrão de localização máxima fornecido abaixo:

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

de fato funcionará sem modificações, desde que:

  • qualquer par de elementos pode ser comparado e
  • é garantido que a entrada contém um elemento máximo, ou seja, um elemento que é emparelhado maior do que qualquer outro elemento na entrada.

(O primeiro pressuposto acima realmente pode ser relaxada, mesmo sem ter que modificar o algoritmo, desde que assumimos que o elemento máxima é comparável com todos os outros elementos e que x > yé sempre false se os elementos xe ysão incomparáveis.)

Em particular, você afirma que:

[…] Para ter certeza de uma resposta, o elemento precisa ser explicitamente comparado a qualquer outro elemento (porque a comparação não é transitiva).

não é verdade sob as premissas fornecidas acima. De fato, para provar que o algoritmo acima sempre encontrará o elemento máximo, basta observar que:

  1. desde que o loop itere sobre todos os elementos de entrada, em alguma iteração x será o elemento máximo;
  2. como o elemento máximo é maior em pares do que qualquer outro elemento, segue-se que, no final dessa iteração, m será o elemento máximo; e
  3. como nenhum outro elemento pode ser emparelhado maior que o elemento máximo, segue-se que mnão será alterado em nenhuma das iterações subsequentes.

Portanto, no final do loop, msempre será o elemento máximo, se a entrada contiver um.


Ps. Se a entrada nem sempre necessariamente contém um elemento máximo, a verificação desse fato exigirá um teste da resposta do candidato em relação a qualquer outro elemento para verificar se ele é realmente máximo. No entanto, ainda podemos fazer isso em O ( n ) tempo após a execução do algoritmo de localização máxima acima:

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

(Estou assumindo aqui que a relação >é irreflexiva, ou seja, nenhum elemento pode ser maior que ele próprio. Se esse não for necessariamente o caso, a comparação x > mna etapa 2 deve ser substituída por x ≠ m and x > m, onde denota comparação de identidade. Ou podemos aplicar a otimização indicado abaixo.)

Para provar a correção dessa variação do algoritmo, considere os dois casos possíveis:

  • Se a entrada contiver um elemento máximo, a etapa 1 a encontrará (como mostrado acima) e a etapa 2 a confirmará.
  • Se a entrada não contiver um elemento máximo, a etapa 1 acabará escolhendo algum elemento arbitrário como m. Não importa qual elemento seja, pois, em qualquer caso, não será o máximo e, portanto, a etapa 2 detectará isso e retornará None.

Se armazenado o índice mna matriz de entrada a, poderíamos realmente passo otimizar 2 para verificar apenas aqueles elementos que vêm antes mde a, já que qualquer elementos posteriores já foram comparados com mna etapa 1. Mas essa otimização não altera a complexidade de tempo assintótica do algoritmo, que ainda é O ( n ).

Ilmari Karonen
fonte
3
De fato, o OP pula muitos detalhes. Por exemplo, nada é dito sobre a reflexividade da relação e, portanto, se não é reflexiva, if x > m:é indefinida.
Fade2black #
4

O(n)

Se você percorrer sua lista comparando elementos, qualquer elemento que "perca" uma comparação pode ser imediatamente descartado, pois, para ser o maior, ele deve ser maior que TODOS os outros elementos para que a perda única o desqualifique.

n1

Esta solução é ativada por uma sutileza: "Nenhum elemento pode ser igual" combinado com o fato de que sempre haverá um elemento maior. Se mapearmos as relações de vitórias como um gráfico direcionado, ficará claro que podemos alcançar o maior elemento simplesmente seguindo as vitórias.

Danikov
fonte
1
" Gráfico direcionado acíclico " é o modelo errado: deveria ser " torneio ". Ciclos são permitidos, e é crucial que todas as arestas existam exatamente em uma direção.
Peter Taylor
@PeterTaylor você está absolutamente certo, eu estava pensando apenas nas vitórias que levam ao elemento 'maior', as outras vitórias são menos relevantes, mas podem ser percorridas no caminho para descobrir as melhores, para que você tenha razão ' t ser descontado
Danikov
3

Suponho que a relação antissimétrica para pelo menos um elemento único (que garante a existência do maior elemento), caso contrário, a tarefa é impossível. Se todos os elementos no conjunto finito forem comparáveis, o procedimento usual de encontrar o máximo funcionará.

Se alguns elementos não forem comparáveis, o procedimento a seguir 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

A,B,C,D

A>B,B>C,C>A
D>A,D>B,D>C


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

m>aa<mamm<aamam

fade2black
fonte
Eu não acho que o primeiro else ifseja necessário. Ele não pode ser acionado se maxfor o máximo, e se o máximo ainda não foi encontrado, não importa qual seja o valor max.
rici
Sim, esse é o primeiro. O outro é o segundo :) :)
rici
Você quer dizer deixar ifs sem elses? É apenas um hábito: com elses nem sequer comparamos. :)
fade2black
1
Não seria mais simples inicializar apenas maxqualquer elemento da lista e, dentro do loop, fazer if max and a[i] are comparable and max < a[i] then max = a[i](onde a primeira parte da condição poderia ser omitida se assumirmos que tentar comparar dois elementos incomparáveis ​​sempre gera falso)?
Ilmari Karonen
1
@badallen, o OP assume que sempre existe o melhor elemento. No seu exemplo, não há maior elemento.
Fade2black 21/11
2

A<BB<A

A1...AnAi<Aj

n2

Ai<Ajj

j0Ai<Aj0ijijAi<AjiijAij<Ajj0ij

Espero que isso seja um pouco compreensível. Sinta-se livre para perguntar nos comentários ou editar.

A idéia básica é que você não pode reunir nenhuma informação sobre os elementos restantes daqueles que você já conhece se permitir uma relação completamente arbitrária.

O argumento ainda funciona se não permitirmos A<Ann2n

Corinna
fonte
1

A > Bn

O(n)

catraca arrepiante
fonte