Voilà j'ai eu l'occasion lors d'un partiel de me confronter a un problème dont je ne trouve toujours pas la solution
Le sujet était formulé de la façon suivante :
 
----------------------------------------------------------------
 
Soit un tableau non trié d'entiers relatifs de taille N.
On souhaiterait savoir si oui ou non, ce tableau contient un nombre présent au moins N/2 fois.
Ecrire l'algorithme correspondant. Celui-ci devra avoir une complexité maximale de O(n).
 
Exemple :
 
soit le tableau suivant :
 
-1 2 3 8 9 8 5 8 6 1 => tableau de taille 10 ne présentant pas d'occurences présentes au moins 5 fois. L'algorithme retournera faux.
 
-10 -5 3 3 5 3 5 3 6 3 => tableau de taille 10 présentant une occurence (le chiffre 3) présent au moins 5 fois. L'algorithme retournera vrai.
 
----------------------------------------------------------------
 
Au niveau de la compréhension du sujet, ça paraissait très clair, mais en ce qui concerne l'algorithme en complexité de O(n) c'est autre chose
Une solution ?

ben il te faut un autre tableau associatif tab[i] -> nb_occurences
après c'est tout bête, tu parcours 1 fois pour le comptage, dès qu'un total dépasse N/2, c'est gagné

 
Moi je ne vois pas mieux (niveau complexité algorithmique parcequ'au niveau de la mémoire c'est naze)
 
Ps : je ne sais plus, O(2n) c'est bien considéré comme équivalent à 0(n)  (parceque l'algo est en 0(2n) dans le pire des cas)
 

 
effectivement c'est ce que certain ont fait...mais cette solution ne marche que partiellement d'une part et même s'il s'agit d'une complexité de O(n) en perf, la complexité mémoire est importante ce qui reste une solution "ridicule".
 
1 - ton tableau temporaire devrait être de taille 2 * MAX_INT
dans le pire des cas (valeurs comprise entre -MAX_INT et +MAX_INT) => impossible d'allouer un tel tableau
 
2 - rien qu'une déclaration tel que : entier tab [100000000] représente un tableau de taille presque de 400Mo en mémoire. un tel tableau pourrait gérer un tableau initial dont l'écart entre le min et le max n'est pas plus grand que 100 000 000.
 
Bref la prof ne s'attendait pas a une telle solution je pense même si dans l'absolu, l'énoncé est respecté.
 
Piste: en fin de partiel, elle m'a dit que la solution etait d'utiliser un tri rapide modifié...comment faire alors

non, avec une table de hachage, la complexité amortie est linéaire.
cela dit la solution grosse consommatrice de mémoire est valide

 
oui, mais je ne suis vraiment pas sur que tu aurais tous les points avec cette solution car elle ne s'attend pas a des algos autant "ridicule" que tu ne songeras même pas une minute à utiliser.
Elle n'est pas assez stupide pour nous "apprendre" a coder ainsi en gros (du moins je l'espère)

1) il n'est pas ridicule
2) je comprends pas la solution tableau associatif est valide

moi je suis content perso

 
fait le avec un tableau de 2 cases contenant chacune -MAX_INT et +MAX_INT (inclure <limits.h> )...et soit patient pour le swap

« tableau associatif »

si tu crées un tableau de 2*MAX_INT pour gérer ça t'as vraiment un pb hein!

 
c'est ce que fait son algo je te signale  

 
c'est quoi alors ce que tu appelles un « tableau associatif »   ?

Et ça te vient pas à l'esprit que tu as peut-être mal compris?

Il me semble que la solution de Taz est efficace, rationnelle et réaliste. Je ne vois pas en quoi elle serait impraticable.
Maintenant, la question existentielle que je me pose, c'est: est-ce qu'un tableau ASSOCIATIF est un "objet" algorithmique? Je veux dire, quelque part il contient déjà une forte implémentation en lui-même, dans son principe de fonctionnement. Est-ce qu'il est valide d'instituer une telle "machinerie" dans un algorithme?  
 
(Je demande ça en toute humilité car je n'ai malheureusement pas étudié l'algorithmique dans son formalisme).

Tout à fait. D'autre part dans le pire des cas, la compexité sera en O(n²) : si tout tes nombres se retrouvent hachés dans la même case. Ceci dit je ne vois pas d'autre solution.

Il y a peut-être une proriété à exploiter : la distance max entre 2 représentants du nombre est bornée, mais je vois pas comment exploiter ça (d'autre part, le nombre on s'en fout).

Oui mais il s'agit de trouver une solution en O(n)...
 
A l'instar de nraynaud, je suspecte qu'il y a d'autres pistes à explorer que celle du tableau associatif. L'exercice proposé peut-il avoir été créé pour déboucher seulement sur ça!? Où se situerait la pédagogie du problème? Où se situerait la réflexion algorithmique?
 
Il y a des données qui ne sont pas innocentes dans l'exposé: pourquoi le critère se situe-t-il à n/2 occurrences?
 
Comme le souligne nraynaud, le pb ne consiste en rien à découvrir le (ou les) nombre(s) (n/2)-redondants (dans une séquence de taille 2p, un cas limite satisfaisant serait que 2 entiers occupent chacun p emplacements -- cependant notons qu'il ne peut pas y avoir plus de 2 nombres présents n/2 fois).
 
Ainsi, il est probable que l'enjeu ne consiste pas essentiellement à découvrir l'identité du nombre redondant (ou des 2), mais plutôt à bâtir une mécanique de calcul qui estime la seule éventualité de son existence. Et une des logiques serait de retourner le pb et de se demander à partir de quelle condition lors de l'exploration de la séquence il NE PEUT PLUS Y AVOIR un nombre (n/2)-redondant...
 
Les entiers fournis sont "relatifs", ce qui engage à faire des calculs de "différences". Là encore ça m'étonnerait que ce soit innocent.
 
Prenons la séquence suivante (pour n=10):
 
S = ( 100 , 5 , -3 , 5 , 100, -3 , 5 , 9 , 5 , 5 )
 
En faisant le calcul des différences mutuelles et en considérant que la chaîne est circulaire (le 5 de fin précède le 100 de début), on obtient la séquence "différentielle" suivante:
 
Sd = ( 95 , -95 , -8, 8 , 95, -103, 8 , 4 , -4, 0 )
 
Appelons "sous-séquence invariante" (ssi) toute sous-séquence de Sd dont la somme des termes est nulle. On peut par exemple "partitionner" complètement Sd par les ssi suivantes:
 
( (95,-95) , (-8,8), (95,-103,8) , (4,-4) , 0 )
 
Cette partition de Sd est idéale et traduit n/2 "zéros" qui à mon sens représentent les n/2 instances de "5" dans S.
 
Sur une rotation de Sd
 
  par exemple avec:
  Sd' = ( -95 , -8, 8 , 95, -103, 8 , 4 , -4, 0 , 95 )
 
on peut envisager d'autres partitions par ssi, du genre :
 
( (-95,-8,8,95) , (-103,8,4,-4,0,95) )
 
mais celle-là est moins fructueuses puisqu'elle ne révèle que 2 zéros (les 2 instances de "3" dans S).
 
Bref, l'algo pourrait peut-être s'appuyer sur une recherche de partitions par ssi. Le principe de calcul des différences et des cumuls pourrait peut-être s'effectuer en O(n)...
 
Mais j'ai pas la soluce pour l'instant...

en ce qui concerne le tableau < associatif >, le concept de cette algo, est-il le meme que celui du tri par comptage ? (qui considere une valeur du tableau initial comme un indice du tableau temporaire (tableau que vous appeleriez associatif)
 
c ca ?  

yep, sauf que comme les valeur du tableau de départ sont potentiellement très grandes, on utilise une fonction qui les ramène à des valeurs raisonables, ce qui peut produire des "collisions", deux valeurs de départ différentes qui auraient une valeur rédiute identique. Il existe plein de méthodes pour résoudre ça, mais elles sont quasiment toutes en O(nombre d'éléments dans le tableau) dans les cas pathologiques. Quand les cas pathologiques sont trop importants, soit on change la fonction de réduction (fonction de hachage) soit on passe à l'arbre binaire équilibré qui n'a pas de cas pathologique.
 
(j'ai tout résumé pour l'application aux entiers qui nous intéresse)

Comme ça a été dit, si un tel nombre existe dans ton tableau, ça veut dire que tu as au plus n/2  valeures distincte dans ton tableau. Donc parcours ton tableau pour ranger les valeures, et dés que tu dépasse n/2 + 1 valeures, retour false.

ouaip, le problème c'est que prendre un valeur et la comparer aux précédentes, ça n'est plus en N. d'ou l'intéret d'utiliser une structure spécifique. cela dit ça fonctionne parfaitement, moi j'ai plus parti dans l'optique « si ce nombre existe, quel est-il ? »

Un tableau associatif est un composant de haut niveau qui sait s'indicer sur n'importe quoi, par exemple des chaînes de cars ...ou des nombres pris au hasard. Il fournit donc une solution simplissime au problème posé puisque, APPAREMMENT, tu peux utiliser les valeurs du tableau initial comme des indices directs sans avoir à faire le moindre tri ni la moindre comparaison entre les nombres. Suffit d'alimenter le conteneur et ça baigne...
 
...MAIS plus j'y réfléchis moins ça me plaît. Les intervenants de ce sujet semblent considérer que ce type de conteneur (le tableau asso) est utilisable en algorithmique. Moi je veux bien, mais il ne faut pas oublier ce qui se passe sous le capot d'un tel composant: CHAQUE opération, notamment l'insertion d'un nouvel élément, est au minimum en O(Log N). Donc c'est un peu facile de camoufler l'implémentation dans une boîte noire et de faire comme si toutes les opérations élémentaires au sein de ce tableau se déroulaient en O(1) et de multiplier ça par les autres opérations de l'algorithme pour obtenir le soi-disant O(N) exigé dans l'énoncé.
 
A ce tarif-là, il suffit d'implémenter tout le programme au sein d'un composant -- appellons-le un résoluteur -- avec en entrée une séquence de nombres, en sortie la réponse OUI ou NON.  
 
Dans ce cas moi je vous résouds votre algo en O(1), en utilisant un résoluteur! Ce n'est pas très sérieux...
 
Bref, il m'est désormais évident que la véritable solution du problème, pour l'instant, nous échappe -- si elle existe!

et la marmotte, elle met le chocolat dans le papier d'alu ?
faut pas confondre implémentation par arbres binaires équilibrés qui nécessite une relation d'ordre et la version table de hachage, dont la complexité d'insertion minimum est O(1) et la complexité max est O(nombre d'éléments déjà présents). la complexité moyenne est un peut bordélique à calculer, sachant qu'elle dépend du taux d'occupation de la table, et de la politique pour les re-hachages.

Le fait qu'on soit obligé de spéculer sur les différentes implémentations possibles du conteneur pour estimer le coût final de l'algorithme montre précisément qu'on est à côté du sujet.
-- Quelle complexité affecter au prétendu algo basé sur le "tableau associatif"?
-- Ca dépend des collisions et du rehachage!
-- Mais bien sûr!
 
NB. - Certes, O(LogN) n'est probablement qu'un chiffre moyen pour les conteneurs associatifs -- au moins il est entre O(1) et O(N).

on donne  à la louche O(1) de moyenne aux algos de table de hachage, et O(n) au pire cas. Et on se prend pas la tête.
Après on fait des tests sur profil si on veut des trucs précis.

T'as raison ne nous prenons pas la tête. Le problème de giz a été soumis dans un partiel d'algorithmique avec une contrainte explicite de complexité maximale de O(n). Les réponses <<à la louche>> avec <<tests sur profil>> doivent certainement être les bonnes... On peut dormir tranquille, Taz a parlé.

attention, faut pas fumer n'importe quoi, ça peut avoir des effets assez étonnants.

je vois pas non plus pourquoi une solution simple et facilement mise en oeuvre serait moins noble (n'est ce pas monsieur occaml(ok, il est nul ce jeu de mots)). j'ai rien prouvé avec mon programme, il me croyait pas, je l'ai programmé et j'ai sorti une trace.

Je parlais pas de ta solution, mais du fait que tout d'un coup il croit que je la défendais.
Pour moi elle est simpliste et n'a rien de fine, je serais vraiment déçu qu'il n'y ait pas mieux. Surtout avec une question formulée de cette manière.

appelez votre tableau <associatif> table de hachage alors j'aurais plus vite compris.
Mais je ne vois pas trop la complexité en O(n) :
Imaginons une fonction de hachage parfaite qui ne provoque aucune collision : cas quasi impossible (ou alors c'est un tri par comptage...comme je l'imaginais au départ) ; dans ce cas on serait effectivement en 0(n) (un seul parcours du tableau initial, insertion de la valeur instantanée dans la table de hachage)
 
Dans le cas de collision, peut on encore considerer l'algo en 0(n) ??? telle est ma question!
 
En effet, prenons une table de hachage au pire de une seule case, les collisions seront donc permanentes et la complexité devient en 0(n²) (pour un element du tableau, on parcours tous les elements dont pointe la case de la table de hachage...on peut imaginer c'est elements stockes dans une liste chainee pointee par cette seule case)
 
Si on imagine que le nombre de collision est tolérable, on sera toujours au dessus de 0(n) met en dessous de 0(n²) => la complexité moyenne ne pourrait etre en 0(n) => enoncé non respecté. je refuterais la réponse de taz alors    
 
qu'en pensez vous ?

pour chaque ensemble de données, il en existe au moins une. Knuth a donné l'algo pour la calculer, mais dans ce cas c'est mort, il faut ajouter la complexité de cet algo à celle de l'autre algo.

 
bon alors personne a de solutions au probleme au final ?  

Non, de mon point de vue.

rien qui ne me satisfasse, mais bon, c'est au prof de décider bordel.

Remarquez un truc : si tu fait une étape de tri rapide, tu obtient 2 sous ensemble de p et q éléments dans lesquels il n'y a pas d'élément commun.
et soit p = q = n/2 auquel cas soit l'un des deux ensembles ne contient qu'une seule valeure, soit retour false.
Sinon, par exemple p > n/2 et tu te refait une étape de tri rapide, et tu regarde à nouveau si un des sous-ensemble à une taille >= n/2.
Faudrait estimer la complexité, mais ça devrait marcher comme truc. (Dés que tu n'as plus que des ensembles de tailles < n/2, retourne false. )

j'ai pas trop poussé du côté de Hoare car très rapidement je suis incapable de calculer la complexité moyenne (je suis une bille en ça). Mais il y a peut-être quelquechose de ce côté (encore qu'un seul étage de l'algo est déjà en O(n) comparaisons).

Ben dans le pire des cas,si tu as un tableau trié par ordre décroissant et tu tape un O(n2) en n/2 étapes de tri rapide. Dans le cas général, t'es bien en O(n), environ 2n comparaisons ( n comparaisons pour la première passe, obtenu 2 sous ensenbles de n/2 éléments sur lesquels tu te retape n/2 comparaisons )

Tu obtiens 2 séquences (u) et (v) disjointes avec p termes d'un côté et q termes de l'autre telles que les ensembles {u} et {v} sont disjoints. Par contre tu ne connais par le cardinal de ces ensembles. Tu sais juste que Card{u}<=p et que Card{v}<=q.
 
Si tu as pris soin de supprimer le pivot en décomptant ses redondances au fur et à mesure (on sait jamais: si c'était lui l'élu), tu peux même te démerder pour que p + q < N ce qui permet de supprimer à coup sûr l'une des deux séquences.
 
Par contre, il suffit qu'on n'ait pas de bol (genre pivot mal choisi dans le tri rapide) pour se retrouver avec (u) riquiqui et tout le problème à nouveau concentré dans (v):
 
(u) = (-1,0) | (v) = (3,5,6,3,6,8,3,3,10,3,3,3)
 
Et même dans le cas excellent où <<l'un des ensembles ne contient qu'une seule valeur>> (càd où une séquence est redondante à 100%), j'aimerais savoir comment on le vérifie sans faire un nouveau parcours?
 
Le O(n) n'est pas encore gagné, là...
Pourtant la philosophie du tri rapide est prometteuse...