Discussion :

[tbc92]

Voici un exemple de programme qui lit un fichier avec la commande BufferedReader : exemple
Lire un fichier est en général une des premières choses que l'on fait quand on apprend un langage de programmation.

Pour trouver cet exemple, j'ai tapé "Java BufferedReader" dans mon moteur de recherche. Et pour trouver le nom de cette commande BufferedReader, j'avais tapé "Java Fichier" dans mon moteur de recherche.
Je ne connais pas du tout Java.

[Guesset]

Bonjour Sandaff,

O(1) temps constant ; est il polynomial?

En général on ne le considère pas comme polynomial même si on pourrait dire qu'il est dépendant d'un polynôme d'ordre 0 (n⁰ = 1)

O(log n) logarithmique; est il polynomial?

Non, il est sub-polynomial car il évolue moins vite que tout polynôme d'ordre supérieur à 0.

O(n) linéaire; est il polynomial?

Oui, polynôme d'ordre 1

O(n × log n) ; est il polynomial?

Non, mais il évolue moins vite que tout polynôme d'ordre supérieur à l'ordre 1

O(n²) quadratique, polynomial

Oui, polynôme d'ordre 2 : par exemple, a.n² + b.n + c.

O(n³) cubique, polynomial

Oui, polynôme d'ordre 3 : par exemple, a.n³ + b.n² + c.n + d.

O(2ⁿ) exponentiel (problèmes très difficiles)

Non, l'évolution exponentielle est plus rapide que tout polynôme d'ordre quelconque. En terme de complexité O(2ⁿ) est équivalent à O(eⁿ) car on ne garde que le critère qui évolue le plus vite sans aucune constante.

Il y a aussi les puissance fractionnaires comme O(n^1/2), O(n^1/3) qui évoluent comme la racine carrée et la racine cubique de n.

La complexité ne donne pas des valeurs de consommation de ressources mais les tendances d'évolutions pour les valeurs importantes en répondant à, par exemple, que se passe-t-il si je passe de 20 000 à 40 000, à 200 000, 2 000 000 ? C'est pourquoi seuls les ordres supérieurs nous intéressent. Il est rare de calculer la complexité quand les valeurs sont faibles sauf si on pressent un comportement exponentiel.

Attention : selon le contexte, un ordre inférieur n'est pas systématiquement meilleur qu'un ordre supérieur. Supposons un algorithme complexe qui a des précalculs importants et se comporte en n² + 1600.n donc en O(n²). Si on le compare à un algorithme de type n³ sans autre coût donc en O(n³),on s'aperçoit qu'en dessous de n=40 c'est ce second algorithme qui est préférable.

Salut

[sandaff]

Monsieur Guesset merci pour vos explications;

En revenant en arrière en ce qui concerne la complexité je vous avoue que c'est au dessus de ma connaissance;

j'ai effectué assez de lecture et je vous ai compris jusqu'ici:

« soit n/(n-u). On voit déjà qu'il y a un problème quand u se rapproche de n »
si u qui est le nombre d'incompatibilité égale à n ; alors il y a une indétermination; mais u=nombre incompatibilité et non le nombre d'étudiants incompatible si je comprend bien;
u peu aussi être supérieur à n qui peu ne pas bloguer aussi le tirage au sort;

exemple: nombre étudiants 50; filles=20; garçons=30; ainsi u=20*30 donc u=600 car toutes les filles seront incompatibles avec tous les garçons;

c'est après cette partie que j'ai perdu totalement le filon: u = a*n et la formule précédente devient 1/(1-a) .

la seconde étape, la sommation, et la transformation en ln, je suis toujours entrain de lire pour pouvoir comprendre;

Seulement je veux savoir:

Un problème de type NP qui doit être transforme en P et si on le transforme en O(n * ln(n)) , ça c'est gagné ou pas?

[Guesset]

Bonjour,

Le nombre d'incompatibilités est toujours relatif au premier membre id1. Combien de personnes sont incompatibles avec id1 ? au maximum c'est n-1 (n si on considère que toute personne est incompatible avec elle même).

Les gens qui sont déjà affectés à un logement sont également à retirer du nombre des prétendants à faire un duo avec id1. Mais attention, u n'est pas égal à la somme des deux car certaines des personnes déjà logées sont aussi incompatibles avec id1. C'est pourquoi, dans la formule, le taux d'incompatibilité a s'applique à (u-2i) et non seulement à u pour tenir compte des 2.a.i logés mais incompatibles avec id1.

La division par zéro traduirait le cas où il n'y a plus de couplage possible avec id1. Les tirages au sort pourraient s'éterniser sans s'en apercevoir. C'est un gros défaut de cet algorithme. Quand il y a peu (voire plus du tout) de couplages possibles, il peut y avoir beaucoup de tirage avant de tomber éventuellement sur un personne compatible. C'est pourquoi j'ai proposé que pour chaque désignation on pratique un tirage initial suivi d'une recherche séquentielle qui boucle.
Illustration avec n = 32 et id1 = 13. Les cas interdits pour id2 sont marquées par X (déjà logés, incompatibles, id1) :

A partir d'un tirage aléatoire d'un premier id2, on passe au suivant en cas d'échec (X). Si on atteint la fin, on continue à 0 (tampon circulaire). Si on retombe sur le id2 tiré au sort, ce n'est pas la peine de continuer : il n' y a pas de solution. En moyenne, à chaque étape on fait (n-2i)(1-a)/2 essais et, au pire, n essais. Jamais plus.

Salutations

[WhiteCrow]

Bonjour Sandaff,

O(1) temps constant ; est il polynomial?

En général on ne le considère pas comme polynomial même si on pourrait dire qu'il est dépendant d'un polynôme d'ordre 0 (n⁰ = 1)

…

Bonjour,
alors il faut faire attention à la notation O («grand Oh»). On dit qu'une fonction g est en O(f) ssi il existe une constante C telle que pour tout x suffisamment grand on ait g(x) < C f(x). On majore uniquement , on n'encadre pas.
Comme on a clairement 1 < 1 x pour tout x>1, on a donc clairement 1=O(n), un temps constant est polynomial.

Ici le signe égal est trompeur et il vaut mieux considérer O(f) comme un ensemble, celui de l'ensemble des fonctions qui vérifient la condition suscitée, et utiliser l'opérateur d'appartenance. On a donc 1 ∈ O(1) ⊂ O(n).

On a également les notation Ω pour la minoration ⇒ g ∈ Ω(f) ssi il existe une constante C telle que pour tout x suffisamment grand on ait g(x) > C f(x).
Et la notation Θ pour un encadrement : g ∈ Θ(f) ⇔g∈O(f) et g∈ Ω(f).

On utilise souvent la notation O car c'est souvent plus simple ; malheureusement c'est souvent le Θ qu'on a en tête.

Quelques autres remarques : on considère souvent aussi que les fonctions manipulées sont toutes à valeurs positives.

Les classes de problèmes (comme L, NL, P, NP, …) utilisent ces notions de complexité mais concernent des problèmes de décisions. Ce n'est que par extension qu'on parle de ces classes dans un cadre plus large. Par exemple, quicksort n'est pas techniquement dans P car ce n'est pas un problème de décision ; tout comme techniquement quicksort (dans sa version classique) n'est pas en Θ(n log n) mais en O(n²) mais aussi en Ω(n log n). Un cas qui illustre le pourquoi de la facilité de la notation O, il est plus simple d'écrire que dans le meilleur cas quicksort est loglinéaire mais quadratique au pire.

[Guesset]

Bonjour WhiteCrow,

...alors il faut faire attention à la notation O («grand Oh»). On dit qu'une fonction g est en O(f) ssi il existe une constante C telle que pour tout x suffisamment grand on ait g(x) < C f(x). On majore uniquement , on n'encadre pas...

Il est facile de confondre 0 et O. Je n'ai pas écrit "O(n⁰ = 1)" qui n'a pas de sens, mais "d'ordre 0 (n⁰ = 1)" la parenthèse n'étant là que pour expliciter, après un espace, l'ordre 0. Excuse moi de t'avoir perturbé. Cela ne retirant rien à la qualité de tes explications.

Tu es sûr que ce n'est pas le plus petit majorant qui respecte les critères énoncés ? Car avec cette définition 1 est aussi en O(n!) etc. ce qui retire beaucoup d'intérêt ao bidule.

Une question cruciale demeure cependant, pourquoi "grand Oh" et pas "grand O" ?

Salut

[sandaff]

Bonjour Mr Guesset

Avant je vous signal qu'une question est toujours en suspens qui doit me permettre d'afficher ici le vrai problème;

et comme c'est démontré que:

1=O(n), un temps constant est polynomial ! une bonne nouvelle alors :

Est-ce la complexité en O(n * ln(n)) ∈ O(n²) ?

merci pour toutes ses explications, maintenant j'ai très bien compris;

Bon j'ai cas même une remarque ici:

« La division par zéro traduirait le cas où il n'y a plus de couplage possible avec id1. Les tirages au sort pourraient s'éterniser sans s'en apercevoir »

si tous les id1, id2, id3, .., sont incompatibles les uns avec les autre alors on doit prévoir à ce niveau une sortie comme le premier cas vous aviez déjà signaler :

« Tiens une question bête. Que se passe-t-il s'il y a un nombre impair d'étudiants et suffisamment de place pour tous ? Et bien, avec la démarche actuelle, il y en aura un qui restera sur le carreau (hormis le fait que la boucle de sélection ne s'arrête pas). Prenons 99 étudiants et 50 chambres et un taux d'incompatibilité assez faible. 98 seulement trouveront une place et la boucle passera en mode infini dès le 99e »

ça c'est déjà corriger et ce second problème même c'est loin de la réalité pourrait être corriger;

maintenant si le nombre de chambres est supérieur aussi aux nombres de compatibilités, alors il faut prévoir une sortie de boucle à ce niveau;

Mais id1 incompatible avec tous les autres n'a aucune incidence sur le tirage;

voilà un exemple ici:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
 
Veuillez saisir le nombre d’étudiants :
10
Veuillez saisir le nombre pair d’étudiant incompatible :
9
Veuillez saisir le nombre d’étudiants à sélectionner par pair càd toatl etudiant ou 2*chambre :
6
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
Veuillez respecter le menu!
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
1
Veuillez saisir l’Id de l’étudiants :
001
Veuillez saisir l’Id de l’étudiants :
002
Veuillez saisir l’Id de l’étudiants :
003
Veuillez saisir l’Id de l’étudiants :
004
Veuillez saisir l’Id de l’étudiants :
005
Veuillez saisir l’Id de l’étudiants :
006
Veuillez saisir l’Id de l’étudiants :
007
Veuillez saisir l’Id de l’étudiants :
008
Veuillez saisir l’Id de l’étudiants :
009
Veuillez saisir l’Id de l’étudiants :
010
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
2
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
002
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
003
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
004
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
005
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
006
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
007
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
008
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
009
Veuillez saisir l’Id de l’étudiant1 incompatible:
001
Veuillez saisir l’Id de l’étudiant2 incompatible:
010
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix : 
3
tabEtudSelect: 004
tabEtudSelect: 005
tabEtudSelect: 006
tabEtudSelect: 009
tabEtudSelect: 008
tabEtudSelect: 002
------Menu principal ---------
   1. Liste d’étudiants     
 2.Liste d’étudiants incompatibles  
  3. Sélection d’étudiants  
           4.Quitter      
      Taper votre choix :

Merci tous les deux ;

Si vous avez votre code ça serra un plaisir quand à moi j'attend la réponse de la question en suspend pour passer au Objet Etudiant et la list;

Je vois qu'il y a un nouveau banc qui m'attende espérons que se termine bien !!!

[WhiteCrow]

Bonjour WhiteCrow,



Il est facile de confondre 0 et O. Je n'ai pas écrit "O(n⁰ = 1)" qui n'a pas de sens, mais "d'ordre 0 (n⁰ = 1)" la parenthèse n'étant là que pour expliciter, après un espace, l'ordre 0. Excuse moi de t'avoir perturbé. Cela ne retirant rien à la qualité de tes explications.

Tu es sûr que ce n'est pas le plus petit majorant qui respecte les critères énoncés ? Car avec cette définition 1 est aussi en O(n!) etc. ce qui retire beaucoup d'intérêt ao bidule.

Une question cruciale demeure cependant, pourquoi "grand Oh" et pas "grand O" ?

Salut

Je ne parlais pas du tout de l'exposant. Juste de la notation «grand Oh» (un anglicisme de la littérature sans doute).

n log n est bien en O(n²) par exemple … tout comme n ou log n ou log* n. Et oui, par définition 1 est en O(n!).

En revanche O(2ⁿ) et O(eⁿ) ne contiennent pas les mêmes fonction O(2ⁿ) ⫋ O(eⁿ) car, par exemple, 2.1ⁿ ∈ O(eⁿ) mais 2.1ⁿ ∉O(2ⁿ). Pourtant tous les problèmes de décisions ayant un algorithme de résolution en O(cⁿ) sont dans la classe EXP (TIME/SPACE suivant ce que l'on mesure).

[sandaff]

Bonsoir Monsieur Guesset;

Si tous les id1, id2, id3, .., sont incompatibles les uns avec les autre et le nombre de chambres qui soit supérieur aussi aux nombres de compatibilités, on les corrige comme suit:

prenons 5 étudiants;
le nombre incompatibles total des Etudiants EI1,2); (1,3); (1,4); (1,5); (2,3); (2,4); (2,5);(3,4);3,5);4,5);
donc EI=C 5 pris 2 à 2; je ne sais pas mettre en exposant; donc c'est la combinaison de 5 pris 2 à 2;
pour n étudiants on a: Combinaison de n pris 2 à 2; EI=n(n-1)/2;
EC=nombre de Compatibilités total des Etudiants; ainsi EI=EC; donc plus EI croit plus EC décroit; la compatibilité et l'incompatibilité sont toujours partagées.

- EI=tabEtudInc.length;
en même temps
- EI=n(n-1)/2;
ce qui veux dire que tous les étudiants sont incompatibles les uns avec les autres;
- EC=n(n-1)/2;
- EI=tabEtudInc.length;
ce qui veux dire que EC=n(n-1)/2-EI; car n(n-1)/2 est partagé entre EC et EI;

voici donc les deux tests:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
 
EI=tabEtudInc.length;
EC=n(n-1)/2-EI;
c = tabEtudSelect.length/2; // Nombre de chambres
 
if(EI==n(n-1)/2)
break loop;
else if (c > EC)
break loop;
else ---

Merci Monsieur WhiteCrow;

n log n est bien en O(n²) par exemple … tout comme n ou log n ou log* n. Et oui, par définition 1 est en O(n!).

Et voilà le problème qui est posé: tiré du site web https://www.techno-science.net

Supposons que vous organisez des logements pour un groupe de quatre cents étudiants universitaires. L'espace est limité et seulement une centaine d'étudiants recevront des places dans le dortoir. Pour compliquer les choses, le doyen vous a fourni une liste de paires d'étudiants incompatibles, et a demandé qu'aucune paire de cette liste n'apparaisse dans votre choix final. C'est un exemple de ce que les informaticiens appellent un problème NP, puisqu'il est facile de vérifier si un choix donné de cent élèves proposé par un collègue est satisfaisant (c'est-à-dire qu'aucun couple pris dans la liste de votre collègue n'apparaît également sur la liste de le bureau du doyen), mais la tâche de générer une telle liste à partir de zéro semble être si difficile qu'elle est complètement irréalisable. En effet, le nombre total de façons de choisir cent étudiants parmi les quatre cents candidats est supérieur au nombre d'atomes dans l'univers connu ! Ainsi, aucune civilisation future ne pourrait jamais espérer construire un supercalculateur capable de résoudre le problème par la force brute ; c'est-à-dire en vérifiant toutes les combinaisons possibles de 100 étudiants. Cependant, cette difficulté apparente ne peut que refléter le manque d'ingéniosité de votre programmeur. En fait, l'un des problèmes en suspens en informatique est de déterminer s'il existe des questions dont la réponse peut être vérifiée rapidement, mais qui nécessitent un temps incroyablement long pour être résolues par une procédure directe. Des problèmes comme celui énuméré ci-dessus semblent certainement être de ce genre, mais jusqu'à présent, personne n'a réussi à prouver que l'un d'entre eux est vraiment aussi difficile qu'il y paraît, c'est-à-dire, qu'il n'y a vraiment aucun moyen réalisable de générer une réponse à l'aide d'un ordinateur. Stephen Cook et Leonid Levin ont formulé indépendamment le problème P (c'est-à-dire facile à trouver) contre NP (c'est-à-dire facile à vérifier) en 1971.

Pour résoudre ce problème je me suis basé sur l'approche de tirage au sort et de tenir compte de 2 étudiants/dortoir qui peut être étendu aussi à n étudiants/dortoir si le prototype est résolu;

Cet algorithme est il situé dans le contexte de ce problème?

Une fois améliorer et optimiser peut il être soumis comme solution de P=NP?

Les apport de chacun sera noté dans la documentation finale;

merci;

[Guesset]

Bonjour WhiteCrow,

Pour que cela soit utile, il faut que le majorant soit le plus proche possible du comportement asymptomatique du traitement. Robert Sedgewick exprime cela en ne gardant que le terme de plus fort poids (aux grandes valeurs) de la fonction de complexité + O(f(n)) pour représenter les autres éléments (négligeable aux fortes valeurs mais souvent très utile pour étudier le pire cas).

Dire que 1 est aussi en en O(n!) n'a pas d'intérêt pratique pour exprimer que, pour n > n₀, la ressource R(n) reste quasiment constante à R_o à partir d'un rang n_o. Alors que O(1) indique bien, par exemple, que R(2n)/R(n) tend vers 1.

De la même manière, si un algorithme est en O(xⁿ), si n grand est multiplié par a, R(a.n)/R(n) tend R_o.(R(n)/R_o)^a. Et cela que x soit 2, 2.1, e, 3, 1515... C'est ce comportement qui caractérise l'appartenance à la famille des complexités exponentielles.

En fait, si en mathématiques, il existe des définitions et des démonstrations non constructives, seules les autres sont utiles au physicien et à l'ingénieur de quelque domaine que ce soit, y compris l'informatique.

Salut

[WhiteCrow]

Bonjour WhiteCrow,

Pour que cela soit utile, il faut que le majorant soit le plus proche possible du comportement asymptomatique du traitement.

Hello,
oui, lorsque cela est possible. Par exemple quicksort est en O(n²) ce qui n'est pas représentatif dans les faits ; d'où les phrases comme : «dans une majorité de cas quicksort est en O(n log n)» sans pour autant dénoter un comportement asymptotique de l'algorithme.
On ne connaît toujours pas bon nombre de minorants théoriques …
Ensuite ce n'est qu'une définition de O (grand Oh). Tu ne peux pas dire que 1 n'est pas en O(n!) car par définition elle l'est. C'est juste comme ça. Je ne dis pas que c'est utile, c'est juste ainsi. C'est également pour cela qu'on dispose d'autres notions comme Ω, Θ, ο (petit omicron), etc.

Robert Sedgewick exprime cela en ne gardant que le terme de plus fort poids (aux grandes valeurs) de la fonction de complexité + O(f(n)) pour représenter les autres éléments (négligeable aux fortes valeurs mais souvent très utile pour étudier le pire cas).

Dire que 1 est aussi en en O(n!) n'a pas d'intérêt pratique pour exprimer que, pour n > n₀, la ressource R(n) reste quasiment constante à R_o à partir d'un rang n_o. Alors que O(1) indique bien, par exemple, que R(2n)/R(n) tend vers 1.

De la même manière, si un algorithme est en O(xⁿ), si n grand est multiplié par a, R(a.n)/R(n) tend R_o.(R(n)/R_o)^a. Et cela que x soit 2, 2.1, e, 3, 1515... C'est ce comportement qui caractérise l'appartenance à la famille des complexités exponentielles.

En fait, si en mathématiques, il existe des définitions et des démonstrations non constructives, seules les autres sont utiles au physicien et à l'ingénieur de quelque domaine que ce soit, y compris l'informatique.

Salut

Attention, les classes comme P, NP, L, NL, BPP et d'autres ne concernent que les problèmes de décisions.

tu as dit :

….
En terme de complexité O(2ⁿ) est équivalent à O(eⁿ) car on ne garde que le critère qui évolue le plus vite sans aucune constante.
…

Ce n'est pas correct (pas définition). On peut néanmoins, pour les problèmes de décisions, définir la classe E des problèmes décidables en 2^O(n) en temps.

[Guesset]

Bonsoir WhiteCrow,

...quicksort est en O(n²) ce qui n'est pas représentatif dans les faits ; d'où les phrases comme : «dans une majorité de cas quicksort est en O(n log n)» sans pour autant dénoter un comportement asymptotique de l'algorithme.

QuickSort n'est pas plus en O(n²) qu'en O(n.ln(n)). Pour qu'il soit en n², il faut une répartition très particulière des cas par rapport à une implémentation donnée (sensibilité au calcul du pivot). Cette répartition serait telle que chaque partition d'un nombre n_i d'éléments engendre deux sous partitions de 1 et n_i-1 éléments. Ce n'est le comportement de l'algorithme que dans le pire des cas (sur n! répartitions). Ce n'est ni un comportement général ni même moyen. A chaque fois que l'aléatoire intervient (ici la distribution de données), le comportement d'un algorithme s'analyse statistiquement. Ici l'optimiste supposera une répartition n_i/2 et n_i/2 et trouvera un algorithme en n.log₂(n). Le calcul classique supposera plutôt une répartition n_i/4 et 3.n_i/4 ce qui donnera quand même un O(n.ln(n)). La complexité de cet algorithme incite à regarder la répartition préalable des donnés. Notamment le QuickSort n'est généralement pas la meilleure solution pour les données quasi triées qui sont très fréquentes (actualisations). Sans pour autant passer en n², il est en concurrence avec des algorithmes plus efficaces dans ces cas là (quasi-linéaires).

.Attention, les classes comme P, NP, L, NL, BPP et d'autres ne concernent que les problèmes de décisions.

Il ne me semble pas avoir parler de classe de problème. Il y a certes un lien entre classe de problème et complexité algorithmique mais ce lien n'est pas si évident sinon tu peux aller chercher ton million de $ chez Cray .

Ce n'est pas correct (pas définition). On peut néanmoins, pour les problèmes de décisions, définir la classe E des problèmes décidables en 2^O(n) en temps.

J'ai cependant montré que la base géométrique n'importe pas pour définir un comportement exponentiel. Par ailleurs, l'expression 2^O(n) me semble oublier un facteur constant qui devrait réapparaître même si la notation ne paraît pas carrée (assimilation d'un ordre à une fonction).

Comme je l'ai dit, l'informaticien, entre autres, cherche des techniques opératoires et délaissent les autres. Tu sais qu'on utilise toujours plus Newton que la relativité pour la plupart des calculs de trajectoires. De même, il faut se souvenir de l'invention mathématiques des distributions pour justifier les opérations que les physiciens faisaient sans vergogne - en physique l'énergie est toujours finie - sur des non-fonctions (Dirac par exemple ). Il y a un dialogue entre mathématiciens et autres scientifiques. Dialogue souvent difficile mais toujours profitable.

En ce qui me concerne, que l'usage de O(f(n)) par les informaticiens soit un peu distant de celui des mathématiciens ne me dérange pas tant qu'elle donne les bons résultats.

Salut

[WhiteCrow]

…
QuickSort n'est pas plus en O(n²) qu'en O(n.ln(n)). Pour qu'il soit en n², il faut une répartition très particulière des cas par rapport à une implémentation donnée (sensibilité au calcul du pivot). Cette répartition serait telle que chaque partition d'un nombre n_i d'éléments engendre deux sous partitions de 1 et n_i-1 éléments. Ce n'est le comportement de l'algorithme que dans le pire des cas (sur n! répartitions). Ce n'est ni un comportement général ni même moyen. A chaque fois que l'aléatoire intervient (ici la distribution de données), le comportement d'un algorithme s'analyse statistiquement. Ici l'optimiste supposera une répartition n_i/2 et n_i/2 et trouvera un algorithme en n.log₂(n). Le calcul classique supposera plutôt une répartition n_i/4 et 3.n_i/4 ce qui donnera quand même un O(n.ln(n)). La complexité de cet algorithme incite à regarder la répartition préalable des donnés. Notamment le QuickSort n'est généralement pas la meilleure solution pour les données quasi triées qui sont très fréquentes (actualisations). Sans pour autant passer en n², il est en concurrence avec des algorithmes plus efficaces dans ces cas là (quasi-linéaires).

Je vais faire simple et court :

• la complexité en temps de quicksort est en O(n²). Il n'y a pas d'aléatoire à considérer (pour autant que cela ait un sens). C'est simplement le pire cas, et quel que soit le nombre d'éléments considérés il y a aura toujours un pire cas (déjà trié par exemple) ;
  
• la complexité en temps dans le meilleur cas est effectivement en O(n log n). Pas d'aléatoire à considérer non plus ;
  
• en moyenne, la complexité est en O(n log n). Toujours pas d'aléatoire à considérer, cela provient simplement du fait que plus le nombre d'éléments à trier est grand moins il y a en proportion de «pires cas» ;
  
• dans les jeux de données «réels» … bah ça dépend des données ;
  
• il y a des moyens de mitiger les pire cas … choix du pivot parmi le médian d'un choix aléatoire de 3 éléments ; là une analyse «probabilistique» prend du sens.

Tous ces faits découlent de la définition de la complexité algorithmique et des notations utilisées. Donc oui,

Il ne me semble pas avoir parler de classe de problème. Il y a certes un lien entre classe de problème et complexité algorithmique mais ce lien n'est pas si évident sinon tu peux aller chercher ton million de $ chez Cray .

Tu parlais de famille en effet, et c'est bien pour cela que je mettais le point sur les problèmes de décisions. La confusion est très, trop, souvent faite.

J'ai cependant montré que la base géométrique n'importe pas pour définir un comportement exponentiel. Par ailleurs, l'expression 2^O(n) me semble oublier un facteur constant qui devrait réapparaître même si la notation ne paraît pas carrée (assimilation d'un ordre à une fonction).

Comme je l'ai dit, l'informaticien, entre autres, cherche des techniques opératoires et délaissent les autres. Tu sais qu'on utilise toujours plus Newton que la relativité pour la plupart des calculs de trajectoires. De même, il faut se souvenir de l'invention mathématiques des distributions pour justifier les opérations que les physiciens faisaient sans vergogne - en physique l'énergie est toujours finie - sur des non-fonctions (Dirac par exemple ). Il y a un dialogue entre mathématiciens et autres scientifiques. Dialogue souvent difficile mais toujours profitable.

En ce qui me concerne, que l'usage de O(f(n)) par les informaticiens soit un peu distant de celui des mathématiciens ne me dérange pas tant qu'elle donne les bons résultats.

Salut

Alors il ne faut pas confondre informaticien et développeur ou programmateur ou …
L'algorithmique est de l'informatique mais aussi des mathématiques. Les notations ont un sens. Les questions, même maladroites de Sandaff, ont une réponse précise. Les réponses que tu as apportées ne sont pas toutes correctes, je ne faisais que le souligner.
Comme je le notais dans une réponse précédente, nombre d'«informaticiens» actuels ne sont que trop familiarisés avec l'algorithmie. Souvent la notation O est mal comprise ou interprétée.

[Guesset]

Bonjour WhiteCrow,

La définition de O amène effectivement à O(n²) pour le Quicksort. Mais la consommation de ressource du Quicksort n'est pas seulement une fonction de n mais aussi de la distribution des données. Négliger cela amène toujours à définir le pire des cas comme argument de complexité. C'est mathématiquement correct mais informatiquement très insuffisant. Le pire cas est intéressant et utile mais ne caractérise pas l'algorithme par rapport aux autres. Prendre en comptes les autres éléments (ici la distribution des données) altérant les performances est donc nécessaire. Que l'on utilise (toi y compris) la même notation pour des distributions diverses est certes dommageable mais n'empêche pas le travail de qualification nécessaire.

"il y a aura toujours un pire cas (déjà trié par exemple)"
Non. Le pire des cas n'est pas systématiquement sur les données déjà triées, tout dépend du calcul du pivot. Par exemple, sur un ensemble trié (même en ordre opposé à celui cherché) le Quicksort est en n.ln(n) si le pivot est la demi-somme de la 1ère et dernière valeur.

"La complexité en temps dans le meilleur cas est effectivement en O(n log n)".
Non. Le meilleur des cas offre une consommation de temps en n.log₂(n). Le pire comme le meilleur sont des extrema qui méritent des expressions précises.

"Il n'y a pas d'aléatoire à considérer"
Si les données à trier n'étaient pas distribuées avec plus ou moins d'aléa, il y aurait une fonction linéaire (en temps) pour les réordonner. De plus, il n'est généralement même pas possible de connaître le taux d'aléa a priori pour tenter de simplifier le problème.

J'aime bien "en moyenne, la complexité est en O(n log n). Toujours pas d'aléatoire à considérer,..." La moyenne est une approche statistique. Chercher l'erreur.

Les données "réelles" s'opposent à des données "fictives" ? Cela suppose que la distribution des données de test ne sont pas représentatives ? Le but d'un tri reste de trier des données réelles, pas de concevoir le jeu de test qui aboutira au pire cas ou au meilleur.

Mes réponses étaient correctes en restant au plus près de la complexité asymptotique de l'algorithme comme tu le fais quand tu écris que le QuickSort est en O(n²) au lieu de O(n³) ou tout autre exposant.

Salut

[WhiteCrow]

Bonjour WhiteCrow,

La définition de O amène effectivement à O(n²) pour le Quicksort. Mais la consommation de ressource du Quicksort n'est pas seulement une fonction de n mais aussi de la distribution des données. Négliger cela amène toujours à définir le pire des cas comme argument de complexité. C'est mathématiquement correct mais informatiquement très insuffisant. Le pire cas est intéressant et utile mais ne caractérise pas l'algorithme par rapport aux autres. Prendre en comptes les autres éléments (ici la distribution des données) altérant les performances est donc nécessaire. Que l'on utilise (toi y compris) la même notation pour des distributions diverses est certes dommageable mais n'empêche pas le travail de qualification nécessaire.

Comme je le disais dans mon premier message, je parle de quicksort classique (celui de Hoare), les pires cas sont alors effectivement des données déjà triées ou triées en ordre inverse.
La complexité d'un algorithme quand on la donne sans précision est toujours celle du pire cas.
Dans le cas d'algo de tri par comparaison, la complexité usuelle (celle que l'on donne sans plus de précision) est toujours temporelle et évalue le nombre de comparaison en fonction du nombre de données à trier.

"il y a aura toujours un pire cas (déjà trié par exemple)"
Non. Le pire des cas n'est pas systématiquement sur les données déjà triées, tout dépend du calcul du pivot. Par exemple, sur un ensemble trié (même en ordre opposé à celui cherché) le Quicksort est en n.ln(n) si le pivot est la demi-somme de la 1ère et dernière valeur.

cf ci-dessus, et le dernier alinéa de mon message précédent que tu ne cites pas.

"La complexité en temps dans le meilleur cas est effectivement en O(n log n)".
Non. Le meilleur des cas offre une consommation de temps en n.log₂(n). Le pire comme le meilleur sont des extrema qui méritent des expressions précises.

Heu … alors soit je ne te comprends pas, soit tu ne comprends pas la notation O … la base du logarithme ne joue en rien ici …

"Il n'y a pas d'aléatoire à considérer"
Si les données à trier n'étaient pas distribuées avec plus ou moins d'aléa, il y aurait une fonction linéaire (en temps) pour les réordonner. De plus, il n'est généralement même pas possible de connaître le taux d'aléa a priori pour tenter de simplifier le problème.

J'aime bien "en moyenne, la complexité est en O(n log n). Toujours pas d'aléatoire à considérer,..." La moyenne est une approche statistique. Chercher l'erreur.

L'erreur est de se dire que probabilité et statistique sont deux choses identiques, sans doute.
Ici on moyenne la complexité en considérant l'ensemble des permutations.

Bon je reprends la partie d'où tu extrais cette phrase :

…

• la complexité en temps de quicksort est en O(n²). Il n'y a pas d'aléatoire à considérer (pour autant que cela ait un sens). C'est simplement le pire cas, et quel que soit le nombre d'éléments considérés il y a aura toujours un pire cas (déjà trié par exemple) ;
  
  …

…

ah ben, je t'ai déjà répondu un peu plus haut …

Les données "réelles" s'opposent à des données "fictives" ? Cela suppose que la distribution des données de test ne sont pas représentatives ? Le but d'un tri reste de trier des données réelles, pas de concevoir le jeu de test qui aboutira au pire cas ou au meilleur.

Donc la partie dont tu parles est dans :

…

• la complexité en temps de quicksort est en O(n²). Il n'y a pas d'aléatoire à considérer (pour autant que cela ait un sens). C'est simplement le pire cas, et quel que soit le nombre d'éléments considérés il y a aura toujours un pire cas (déjà trié par exemple) ;
  
• la complexité en temps dans le meilleur cas est effectivement en O(n log n). Pas d'aléatoire à considérer non plus ;
  
• en moyenne, la complexité est en O(n log n). Toujours pas d'aléatoire à considérer, cela provient simplement du fait que plus le nombre d'éléments à trier est grand moins il y a en proportion de «pires cas» ;
  
• dans les jeux de données «réels» … bah ça dépend des données ;
  
• il y a des moyens de mitiger les pire cas … choix du pivot parmi le médian d'un choix aléatoire de 3 éléments ; là une analyse «probabilistique» prend du sens.

Alors ne mélangeons pas deux choses :

• déterminer les complexité en temps dans différents cas de figures ; et ici on est bien obligé de «déterminer» quel jeu de donné aboutit au pire cas … soinon on ne parlerait pas de pire cas ;
• avoir des informations sur un jeu de données IRL qui permet de décider en connaissant les différentes complexité quel algorithme sera le plus adapté aux contraintes IRL.

Mes réponses étaient correctes en restant au plus près de la complexité asymptotique de l'algorithme comme tu le fais quand tu écris que le QuickSort est en O(n²) au lieu de O(n³) ou tout autre exposant.

Salut

Non.
Mais reprenons tes réponses si tu le souhaites :

1. faux ; O(1) ⊂O(n), donc les fonctions constantes sont polynomiales ;
2. faux ; O(log n) ⊂ O(n) ; j'en profite pour rappeler que la base du log n'est pas déterminante … et que je ne comprends toujours pas ton message …
3. correct
4. faux ; O(n log n) ⊂ O(n²)
5. 6. corrects
7. dur à juger ta réponse, sinon que O(2ⁿ) ⫋ O(eⁿ).

[Guesset]

Bonjour WhiteCrow,

"Lorsqu'on dispose d'une borne supérieure asymptotique, on utilise la notation O." Thomas Cormen, Charles Leiserson, Ronald Rivest dans "Introduction à l'algorithmique".

Il y a quelque chose qui t'échappe dans asymptotique ?

Je confirme ce que j'ai écrit.

Salut

[sandaff]

Bonjour Monsieur WhiteCrow;

Je viens de me réveiller et il parait que des choses inintéressantes se sont passé à mon insu;

Les questions, même maladroites de Sandaff, ont une réponse précise.

Vous pouvez être un peu plus précis ou détaillant;

Vous saviez moi je ne suis pas balaise en complexité et j'ai appris dans le tas sur cette question;

Mais j'ai respecté l'aide de Monsieur Guesset car j'étais bloqué sur le fait que moi je cherchais à déterminer les opérations élémentaires ligne par ligne;

et une fois dans la boucle j'étais confronté de l’aléatoire et la boucle for, do-while et la recherche dans un tableau n'ont trié et pourtant vous deux, vous parlez tout le temps de Quicksort ;

J'ai trouvé sa réponse plus raisonnable que j'ai abandonné mes démarche à ce niveau;

Donc si quelle que chose sonne mal dans toutes ses réponses vous aviez tout le loisir d'apportez votre solution au lieu de faire passer la discussion en un tribunal surtout que il y a toujours des question en suspens même si ça parait bête;

Merci;

[Guesset]

Bonjour,

L'inclusion de O(f(n)) n'induit pas celles des fonctions. Si on se limite aux polynômes, un manque de rigueur peut se laisser abuser car l'ensembles des polynômes de degré n inclut les polynômes de degré inférieur ou égal. Mais ce n'est pas une propriété due à l'inclusion des O(P(n)).

Les mathématiques sont subtiles. Il faut comprendre qu'il n'y a pas de transitivité. O(ln(n)) inclus dans O(n) n'implique pas {fonctions_logarithmiques(n)} soit inclus dans {P(n)}. Si c'était le cas, les fonctions logarithmiques seraient des polynômes.

J'espère que c'est clair.

Donc si 1 peut être considéré comme un polynôme de degré 0, il ne le doit nullement à O(1) inclus dans O(n). Et les autres déclinaisons du même type sont tout autant erronées.

Salutations

[WhiteCrow]

Bonjour WhiteCrow,

"Lorsqu'on dispose d'une borne supérieure asymptotique, on utilise la notation O." Thomas Cormen, Charles Leiserson, Ronald Rivest dans "Introduction à l'algorithmique".

Il y a quelque chose qui t'échappe dans asymptotique ?

Tu n'as sans doute pas compris mon premier message … je me permets de te le copier afin que tu puisses le relire et le comprendre.

Bonjour,
alors il faut faire attention à la notation O («grand Oh»). On dit qu'une fonction g est en O(f) ssi il existe une constante C telle que pour tout x suffisamment grand on ait g(x) < C f(x). On majore uniquement , on n'encadre pas.
Comme on a clairement 1 < 1 x pour tout x>1, on a donc clairement 1=O(n), un temps constant est polynomial.

Ici le signe égal est trompeur et il vaut mieux considérer O(f) comme un ensemble, celui de l'ensemble des fonctions qui vérifient la condition suscitée, et utiliser l'opérateur d'appartenance. On a donc 1 ∈ O(1) ⊂ O(n).

On a également les notation Ω pour la minoration ⇒ g ∈ Ω(f) ssi il existe une constante C telle que pour tout x suffisamment grand on ait g(x) > C f(x).
Et la notation Θ pour un encadrement : g ∈ Θ(f) ⇔g∈O(f) et g∈ Ω(f).

On utilise souvent la notation O car c'est souvent plus simple ; malheureusement c'est souvent le Θ qu'on a en tête.

…

Tu avais sans doute plus un Θ en tête qu' un O …

Parce que, jusqu'à preuve du contraire, toute fonction constante est dominée asymptotiquement par la simple fonction n, par exemple ; cela par définition signifie que 1 ∈ O(n) …
Tout comme la fonction log (peu importe la base) est également dominée asymptotiquement par n ; et toujours par définition cela signifie que log n ∈ O(n) …

En fait, quand on affirme qu'un algorithme est linéaire (en temps ou en espace suivant n) cela signifie qu'il est en Θ(n), pas uniquement en O(n). L'utilisation de O est nécessaire quand il n'est pas majoré et minoré par le même ensemble de fonctions. Un algorithme sera en Θ( f(n) ) ssi le pire cas est en O( f(n) ) et le meilleur cas en Ω( f(n) ).

Et effectivement, tu devrais relire le Cormen … tout le chapitre 3 devrait t'être profitable.

Je confirme ce que j'ai écrit.

Salut

Au lieu de confirmer tu pourrais au moins montrer où je me trompe si tel est le cas …
Je l'ai bien fait pour tes interventions.

Bonjour,

L'inclusion de O(f(n)) n'induit pas celles des fonctions. Si on se limite aux polynômes, un manque de rigueur peut se laisser abuser car l'ensembles des polynômes de degré n inclut les polynômes de degré inférieur ou égal. Mais ce n'est pas une propriété due à l'inclusion des O(P(n)).

Les mathématiques sont subtiles. Il faut comprendre qu'il n'y a pas de transitivité. O(ln(n)) inclus dans O(n) n'implique pas {fonctions_logarithmiques(n)} soit inclus dans {P(n)}. Si c'était le cas, les fonctions logarithmiques seraient des polynômes.

J'espère que c'est clair.

Donc si 1 peut être considéré comme un polynôme de degré 0, il ne le doit nullement à O(1) inclus dans O(n). Et les autres déclinaisons du même type sont tout autant erronées.

Salutations

Les mathématiques sont subtiles …
Ici on parle de définitions simples. On applique la définition, on a la réponse ; parfois les mathématiques sont simples.

Puisque tu aimes citer le cormen ⇒


Applique la définition … tu verras que tout sera plus simple.

[Guesset]

Bonjour,

"O(1) ⊂ O(n), donc les fonctions constantes sont polynomiales "

Donc pour toi, l'inclusion des O(f(n)) dans O(g(n) entraîne l'inclusion de l'ensemble des fonctions de type f(n) dans l'ensemble des fonctions de type g(n). Donc l'ensemble des fonctions logarithmiques est inclus dans l'ensemble des polynômes de degré supérieur ou égal à 1.

C'est tellement faux que ça n'a pas d'intérêt d'aller plus loin.

Salutations.