en temps O (n): trouver le plus grand élément de l'ensemble où la comparaison n'est pas transitive

21

Le titre pose la question.

Nous avons en entrée une liste d'éléments que nous pouvons comparer (déterminer lequel est le plus grand ). Aucun élément ne peut être égal.

Points clés:

  1. La comparaison n'est pas transitive (pensez aux ciseaux de papier de roche): cela peut être vrai: A> B, B> C, C> A (notez que ce n'est pas une entrée valide car il n'y a pas de réponse valide ici, je ne fais que décrire ce que " comparaison non transitive "signifie)
  2. Chaque tableau d'entrée sera garanti d'avoir une réponse
  3. le plus grand signifie que l'élément doit être supérieur à tout autre élément
  4. La propriété inverse tient à dire A> B implique que B <A

Exemple:

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

Je ne peux pas trouver un moyen de le faire en temps O (n), ma meilleure solution est O (n ^ 2).

Je suis bloqué sur chaque approche car pour être sûr d'une réponse, l'élément doit être explicitement comparé à tous les autres éléments, pour prouver qu'il s'agit bien de la réponse (car la comparaison n'est pas transitive).

Cela exclut l'utilisation d'un tas, le tri, etc.

James Wierzba
la source
8
On ne sait pas comment "le plus grand élément" serait défini? Par exemple, quel élément est le plus grand si ? Avez-vous d'autres règles de comparaison? UNE>B,B>C,C>UNE
fade2black
6
Je ne peux pas imaginer comment nous sélectionnerions le plus grand élément d'un ensemble qui n'est pas au moins partiellement ordonné. Veuillez consulter la définition du plus grand et du moins élément. Le manque de transitivité exclut un ordre partiel.
fade2black
3
@ fade2black Pourquoi me liez-vous à une autre définition de "plus grand". J'énonce explicitement la définition de la plus grande pour le contexte de cette question. Le plus grand moyen, l'élément est supérieur à tous les autres éléments. Aucun élément n'est égal. C'est tout ce qu'il y a à faire. N'est-ce pas clair?
James Wierzba
2
Votre dernier exemple avec A, B, C, D serait utile pour comprendre votre question si vous l'incluiez dans votre PO.
fade2black
3
Un membre de l'équipe du compilateur C # avait l'habitude de poser cela comme une question d'entrevue; il est pertinent car en C #, l'algorithme de résolution de surcharge doit choisir le meilleur membre unique d'un ensemble étant donné une relation de "bêtise" qui est habituellement, mais pas nécessairement transitive. (Ou donnez une réponse appropriée s'il n'y a pas de meilleur membre unique; les liens sont possibles.) Bien que j'aie réussi à y répondre correctement, je n'ai jamais pensé que c'était une question d'entrevue particulièrement bonne car elle s'appuie sur un aperçu "aha" pour obtenir le algorithme linéaire.
Eric Lippert

Réponses:

38

L'algorithme standard pour trouver un maximum fonctionne toujours. Commencez par et passez en revue les éléments, si vous voyez une valeur plus grande, mettez à jour le maximum pour être cette valeur. La raison pour laquelle cela fonctionne est que chaque élément que vous avez ignoré est plus petit qu'au moins un élément et ne peut donc pas être le maximum.a1

Pour être clair, par «algorithme standard», je veux dire ce qui suit:

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

Pour être complet, je vais discuter ici des questions soulevées dans les commentaires. Le paramètre de la discussion ci-dessus consiste à trouver un maximum par rapport à une relation antisymétrique , où a i est un maximum si pour tout j i nous avons a i > a j . L'algorithme ci-dessus fonctionne en supposant qu'un maximum existe, mais si cela n'est pas connu, on peut l'utiliser pour vérifier l'existence d'un maximum (vérifier si l'élément retourné est en effet supérieur à tous les autres éléments, cela est mentionné dans le commentaire de Chi et dans la réponse d'Ilmari Karonen).<aijiai>aj

Si n'est pas nécessairement anti symétrique, alors l'algorithme ci-dessus échoue (comme Emil l'a mentionné dans les commentaires). Si < est une relation arbitraire (c'est-à-dire que nous assouplissons à la fois la transitivité et l'anti-symétrie), il n'est pas difficile de montrer qu'il n'est pas possible de trouver un maximum en temps linéaire. On note # un i le nombre de fois un i participé à une requête, nous définissons une relation contradictoire d'une manière que le maximum ne peut être révélé sans suffisamment de requêtes. Étant donné la requête a i > ? a j , répondez a i > a j si # a i<<#aiaiuneje>?unejuneje>unej et a i < a j sinon. Si le nombre de requêtes est o ( n 2 ) , alors un maximum n'a pas encore été vu, et il peut être défini pour être l'un des éléments de l'ensemble.#uneje<n-1uneje<unejo(n2)

Ariel
la source
1
@JamesWierzba (je pense), il signifie simplement qu'un élément "ignoré" est un élément qui n'est pas supérieur à votre max actuel. Considérez l'algorithme standard: vous comparez chaque valeur de votre liste au maximum actuel. Vous avez dit qu'il y a un plus grand élément dans chaque liste. À un certain point, vous comparerez cela à votre maximum actuel, et comme il est plus grand, cette valeur devient votre nouveau maximum. Étant donné que cette valeur est supérieure à tout le reste de la liste, vous ne trouverez jamais d'élément supérieur et votre valeur maximale ne sera pas remplacée. Après vos ncomparaisons, votre max actuel doit être la réponse
Lord Farquaad
1
Modifié pour plus de clarté, cet algorithme ne suppose pas de transitivité. Si vous trouvez cela difficile à croire, suivez les détails de la preuve d'exactitude (supposez à des fins de contradiction que la valeur retournée n'est pas le maximum et utilisez l'idée du premier paragraphe).
Ariel
7
Cela repose sur l'hypothèse 2 de la question: il y a toujours un maximum dans le tableau. Si ce n'était pas le cas, maxne pourrait être que le maximum d'un sous-tableau. Pourtant, même sans l'hypothèse 2, on peut trouver un maximum provisoire, puis le vérifier sur l'ensemble du tableau à l'aide d'un deuxième balayage, dans la limite O (n).
chi
7
Cette réponse suppose que et B > A ne peuvent pas tenir en même temps. Pour autant que je sache, cela n'est pas exclu dans la question. A>BB>A
Emil Jeřábek soutient Monica
4
@ oconnor0 Cela ne suit pas. Pour un exemple concret, supposons A> B, A> C, B> A et C> B. Alors A est supérieur à tout autre élément de l'ensemble (et est le seul élément avec cette propriété), mais si les éléments sont rencontré dans l'ordre A, B, C, l'algorithme affichera C.
Emil Jeřábek prend en charge Monica
24

Comme le note Ariel , l'algorithme de recherche de maximum standard donné ci-dessous:

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

fonctionnera en fait sans modification tant que:

  • n'importe quelle paire d'éléments peut être comparée, et
  • l'entrée est garantie pour contenir un élément maximal, c'est-à-dire un élément qui est par paire plus grand que tout autre élément dans l'entrée.

(La première hypothèse ci-dessus peut en fait être assouplie, même sans avoir à modifier l'algorithme, tant que nous supposons que l'élément maximal est comparable à tous les autres éléments et cela x > yest toujours faux si les éléments xet ysont incomparables.)

En particulier, vous affirmez que:

[…] Pour être certain d'une réponse, l'élément doit être explicitement comparé à tous les autres éléments (car la comparaison n'est pas transitive).

n'est pas vrai dans les hypothèses données ci-dessus. En fait, pour prouver que l'algorithme ci-dessus trouvera toujours l'élément maximal, il suffit de constater que:

  1. puisque la boucle itère sur tous les éléments d'entrée, à une certaine itération xsera l'élément maximal;
  2. puisque l'élément maximal est deux par deux plus grand que tout autre élément, il s'ensuit qu'à la fin de cette itération, mil sera l'élément maximal; et
  3. Puisqu'aucun autre élément ne peut être deux par deux plus grand que l'élément maximal, il s'ensuit que mcela ne changera sur aucune des itérations suivantes.

Par conséquent, à la fin de la boucle, msera toujours l'élément maximal, si l'entrée en contient un.


Ps. Si l'entrée ne contient pas nécessairement toujours un élément maximal, la vérification de ce fait nécessitera en effet de tester la réponse candidate par rapport à tous les autres éléments pour vérifier qu'elle est vraiment maximale. Cependant, nous pouvons toujours le faire en temps O ( n ) après avoir exécuté l'algorithme de recherche de maximum ci-dessus:

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

(Je suppose ici que la relation >est irréflexive, c'est-à-dire qu'aucun élément ne peut être supérieur à lui-même. Si ce n'est pas nécessairement le cas, la comparaison x > mde l'étape 2 devrait être remplacée par x ≠ m and x > m, où dénote une comparaison d'identité. Ou nous pourrions simplement appliquer l'optimisation noté ci-dessous.)

Pour prouver l'exactitude de cette variation de l'algorithme, considérons les deux cas possibles:

  • Si l'entrée contient un élément maximal, alors l'étape 1 le trouvera (comme indiqué ci-dessus) et l'étape 2 le confirmera.
  • Si l'entrée ne contient pas d'élément maximal, alors l'étape 1 finira par choisir un élément arbitraire comme m. Peu importe de quel élément il s'agit, car il sera en tout cas non maximal, et donc l'étape 2 le détectera et le retournera None.

Si nous stockons l'indice mdans le tableau d'entrée a, on pourrait en fait pas optimize 2 pour vérifier que les éléments qui viennent avant mdans a, puisque les éléments ultérieurs ont déjà été comparé à l' métape 1. Mais cette optimisation ne change pas la complexité du temps asymptotique de l'algorithme, qui est toujours O ( n ).

Ilmari Karonen
la source
3
En fait, l'OP ignore de nombreux détails. Par exemple, rien n'est dit sur la réflexivité de la relation, et donc si elle n'est pas réflexive alors elle n'est pas if x > m:définie.
fade2black
4

«le plus grand signifie que l'élément doit être plus grand que tous les autres éléments» est une énorme indication sur la façon de procéder dans .O(n)

Si vous parcourez votre liste en comparant des éléments, tout élément qui "perd" une comparaison peut être immédiatement éliminé car, pour être le plus grand, il doit être supérieur à TOUS les autres éléments afin que la perte unique le disqualifie.

n1

Cette solution est rendue possible par une subtilité: "Aucun élément ne peut être égal" combiné avec le fait qu'il y aura toujours un plus grand élément. Si nous cartographions les relations de victoires sous forme de graphique dirigé, il est clair que nous pouvons atteindre le plus grand élément simplement en suivant les victoires.

Danikov
la source
1
" Graphique orienté acyclique " n'est pas le bon modèle: il devrait plutôt s'agir de " tournoi ". Les cycles sont autorisés, et il est crucial que chaque bord existe dans exactement une direction.
Peter Taylor
@PeterTaylor vous avez tout à fait raison, je ne pensais qu'aux victoires qui mènent vers le plus grand élément, les autres victoires sont moins pertinentes mais peuvent être parcourues sur le chemin de la découverte du plus grand pour que vous ayez raison de le faire. t être réduit
Danikov
3

Je suppose que la relation antisymétrique pour au moins un élément unique (qui garantit l'existence du plus grand élément), sinon la tâche est impossible. Si tous les éléments de l'ensemble fini sont comparables, la procédure de recherche de maximum habituelle fonctionne.

Si certains éléments ne sont pas comparables, la procédure suivante fonctionnera

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

UNE,B,C,

UNE>B,B>C,C>UNE
>UNE,>B,>C


je=1: max=UNE
je=2: max=UNEUNE>B
je=3: max=CUNE<C
je=4: max=>C

m>unea<mamm<aamam

fade2black
la source
Je ne pense pas que le premier else ifsoit nécessaire. Il ne peut pas être déclenché si maxest le maximum, et si le maximum n'a pas encore été atteint, peu importe la valeur de max.
rici
Oui, c'est le premier. L'autre est le deuxième :)
rici
Tu veux dire ifs sans elses? C'est juste une habitude: avec elses on ne compare même pas. :)
fade2black
1
Ne serait-il pas plus simple de simplement initialiser maxà n'importe quel élément de la liste et, à l'intérieur de la boucle, de le faire if max and a[i] are comparable and max < a[i] then max = a[i](où la première partie de la condition pourrait être omise si nous supposons qu'essayer de comparer deux éléments incomparables donne toujours faux)?
Ilmari Karonen
1
@badallen l'OP suppose qu'il y a toujours le plus grand élément. Dans votre exemple, il n'y a pas d'élément le plus important.
fade2black
2

En complément de A<BB<A

A1...AnAi<Aj

n2

Pour la plupart de l'algorithme, l'adversaire s'assurera de toujours retourner vrai pour Ai<Ajj

j0Ai<Aj0ijijAi<AjiijAij<Ajj0ij

J'espère que c'est quelque peu compréhensible. N'hésitez pas à demander dans les commentaires ou à modifier.

L'idée de base est que vous ne pouvez pas collecter d'informations sur les éléments restants à partir de ceux que vous connaissez déjà si vous autorisez une relation complètement arbitraire.

A<Ann2n

Corinna
la source
1

A > Bn

O(n)

monstre à cliquet
la source