Discuter:Comparaison asymptotique
Un article de Wikipédia, l'encyclopédie libre.
Sommaire |
[modifier] Renommage de la page
Je pense pour ma part qu'il serait judicieux de renommer la page en "comparaison asymptotique", ou bien "domination" ou "prépondérance" comme suggérait Aldoo. Il faudrait évidemment créer ensuite des redirections depuis "notations de Landau", "petit O", "grand O", etc ...Pethrus 9 octobre 2007 à 13:09 (CEST)
[modifier] Petit o et renommage de la page
Il manque la notation « petit o », il me semble, qui est tout aussi utilisée que « grand O ». Peut-être faudrait-il aussi ajouter la notation « θ », elle aussi très courante en théorie de la complexité, mais je ne sais pas si on peut l'attribuer à Landau.
Quant au renommage de cette page, proposé dans Projet:Mathématiques, je ne pense pas que ce serait une bonne idée. Si je veux une page sur les chats, c'est bien à Chat que je regarderai. Maintenant, rien empêche des liens ou des redirections depuis Domination ou Prépondérance.
--Aldoo / ✉ 8 jan 2005 à 13:51 (CET)
[modifier] notations de landau
La notation theta(f(n)) ne vient pas de Landau. C'est tout comme OmegaMajuscule(f(n)) une notation utilisée uniquement par les informaticiens, mais je ne connais pas leur origine.
1/ la notation "O" n'est pas de Landau. On la trouve dans le traité de Bachmann Zahlentheorie Tome 2, 1894 (page 402 pour ceux qui veulent vérifier). L'ouvrage est accessible sur gallica.bnf.fr
Landau n'ayant passé sa thèse qu'en 1899, il est donc impossible qu'il ait inventé cette notation avant 1894.
2/ la notation OmegaMajuscule(f(n)) n'est pas utilisée QUE par les informaticiens. Elle est utilisée dans les problèmes d'analyse asymptotique.
Claudeh5 19 juin 2006 à 19:01 (CEST)
[modifier] notation petit o
J'ajoute une définition de la notation petit o.
La structure de l'article n'est vraisemblablement pas définitive, et l'on pourrait compléter avec quelques propriétés, notamment sur les comparaisons grand O / petit o.
[modifier] Confusion o(x) O(x)
L'exemple cité :
Exprime un développement limité en 0 de l'exponentielle qui doit dans ce cas comporter un o(x) et non un O(x), c'est à dire :
- au voisinage de 0
Ce n'est pas à mon avis un bon exemple de la manipulation de la notation O.
- Non, un o(x3) est une fonction qui est négligeable devant x3 ; ici, le reste u développement limité est équivalent à x3/6 et est par conséquent un O(x3) et non un o(x3). Par contre, un O(x3) est lui-même un o(x2). Ekto - Plastor 24 février 2007 à 12:57 (CET)
Effectivement je n'avais pas fait attention au degré dans le O, j'ai d'ailleurs écrit o(x3) au lieu de o(x2). Cependant s'il m'a fait régir c'est qu'il me semble que l'on rencontre plus souvent des o dans les DL plutôt que des grands O. C'est un détail mais quand on ne maîtrise pas (comme moi) cela prête à confusion, non ?!
- Non, en pratique, on ne rencontre pas plus l'un que l'autre. Ekto - Plastor 24 février 2007 à 15:37 (CET)
En général oui, mais pour la définition des développements limités (exemple que je conteste) je maintiens surtout après avoir parcouru : Développement limité et Théorème de Taylor --Alexis 25 février 2007 à 09:21 (CET)
- certain auteurs distinguent des DL et des DL "forts" mais c'est très rare : presque tout le monde s'accorde pour baptiser les deux types des "DL".Peps 3 mai 2007 à 22:23 (CEST)
[modifier] un autre titre
"notation de Landau" ne désigne que o et O. En plus cette désignation est criticable, et pas forcément connue de tous les usagers (certains se contentant de dire petit o, grand O). Pourquoi pas comparaison asymptotique ? des avis ? Peps 3 mai 2007 à 22:37 (CEST)
- Pour ma part, après quelques cours et bouquins j'ai tendance à dire « notations asymptotiques », mais je ne sais pas si c'est l'expression la plus explicite... --Tastalian 18 août 2007 à 12:13 (CEST)
[modifier] proposition de lien externe
Bonjour à tous. J'ai rédigé il y a peu un document sur le [calcul intuitif de complexités] avec la notation « grand O » de Landau. Il est plutôt destiné aux néophytes et tente de proposer quelques règles simples pour estimer le comportement d'algorithmes, et notamment leur temps d'exécution.
Comme l'approche est assez différente de celle de l'article, je propose de l'ajouter en lien externe. S'il en est digne, bien sûr. Vos avis ? --Tastalian 18 août 2007 à 12:13 (CEST)
- Oui, cette approche est intéressante et mérite un lien externe. Mais je pense que si cet article est recyclé dans quelques temps, il serait même nécessaire de faire figurer une partie sur le lien entre ces notations et la complexité algorithmiques, qui se traite un petit peu différemment de la complexité purement mathématique. Votre lien trouverai alors parfaitement sa place. --Pethrus (d) 31 décembre 2007 à 12:24 (CET)