Discussion:Analyse de la complexité des algorithmes

Véracité de la partie sur le pire cas de la deuxième méthode de Exemple de la recherche dans une liste triée

Le dernier paragraphe ne me semble pas correct (dans le pire cas on ne découpe pas en deux mais on obtient une liste de taille n-2), peut-on mettre un avertissement sur la page dans l'attente d'une correction ?

Bonjour,

Je ne comprends pas ce que vous ne comprenez pas, alors je vais essayer d’illustrer avec un exemple. Si je cherche « Zola » dans le Bottin, j’ouvre mon gros bouquin à la page du milieu. Imaginons que j’y lise des noms qui commencent par M. Comme Z vient après M, je sais alors qu’il me suffit de chercher dans la moitié d’annuaire comprise entre cette page et la fin. Si je cherchais plutôt « Hugo », comme H vient avant M, je devrais plutôt chercher dans la première moitié de l’annuaire. Dans les deux cas, je me retrouve à continuer la recherche dans un Bottin deux fois plus petit.

La recherche dichotomique devrait même être connue des écoliers, car je me souviens d’avoir eu des devoirs où il fallait trouver des mots dans le dictionnaire le plus vite possible…

Ce qui me choque un peu par contre, dans cette section, c’est l’emploi du mot « liste ».

Évidemment la terminologie est plus ou moins fluctuante, et moi-même je n’ai pas une connaissance exhaustive des usages, mais à ma connaissance et d’après l’article Wikipédia, une liste en informatique désigne toute structure de données capable de représenter une suite finie (ou pas) d’éléments. Il s’agit d’une description abstraite de haut niveau, sans précision supplémentaire sur le coût de chaque opération, ce qui est problématique pour une analyse de complexité.

Pire, je pense que si quelqu’un dit « liste » avec quelque chose de plus précis en tête, il y a de fortes chances qu’il pense à une liste chaînée. En tout cas, j’ai toujours vu « liste » employé dans ce sens, que ce soit en informatique théorique (dont la complexité fait partie), en programmation fonctionnelle (selon la tradition initiée par Lisp…) ou dans mes cours d’informatique. Or, cette structure de données ne permet pas d’accéder à un élément arbitraire en temps constant, ce qui est crucial pour un algorithme dichotomique. Pour ça, il faut utiliser un tableau par exemple.

Si personne ne me contredit, je corrigerai le vocabulaire de cette section.

— Maëlan 18 décembre 2018 à 20:51 (CET)

Découpage en plusieurs pages, nom des pages

Ce sujet a déjà été maintes fois débattu sur cette page, et je suis donc désolé de remettre le couvert. Cependant, je trouve que l'article actuel est un peu "brouillon" car on y parle un peu de tout et n'importe quoi à la fois. Je vais essayer de m'expliquer. En gros, mon avis sur la question serait de suivre la version anglophone.

Il ne faut pas confondre deux domaines de l'informatique théorique distincts qui sont l' analyse des algorithmes d'une part, et l'étude de la complexité structurelle d'autre part (pour les noms, voir un peu plus bas). Le premier domaine consiste à prendre un algorithme ou une famille d'algorithmes et d'en étudier le temps de fonctionnement par exemple (ou l'espace utilisé). On peut étudier le temps dans le pire cas, en moyenne, en analyse amortie, etc... Pour citer des "papes" du domaine, on peut citer Donald Knuth ou encore le regretté Philippe Flajolet. Le deuxième domaine consiste à étudier les classes de complexité en tant que telles. Si l'objet d'étude dans le premier cas est l'algorithme, dans le deuxième il s'agit plutôt d'étudier le modèle de calcul. D'ailleurs, dans ce domaine, on fait varier le modèle de calcul pour comparer les puissances de calcul obtenus (machine de Turing déterministe, non déterministe, probabiliste, circuit booléen uniforme ou non, modèle de calcul quantique, etc...). C'est le domaine qui pose la question de P versus NP par exemple. On peut bien sûr établir des liens entre les deux domaines, mais ils sont bien distincts. D'ailleurs, les bouquins traitent en général l'un ou l'autre des domaines et pas les deux. De la même façon, les chercheurs des deux domaines ne publient pas vraiment dans les même conférences ou journaux, à part quand il s'agit de conférences ou journaux très généralistes (comme Theoretical Computer Science).

Ce que je propose du coup est de créer une page Analyse de la complexité des algorithmes, et une autre sur la Théorie de la complexité. La page Classes de complexité peut aussi avoir son intérêt mais elle n'est à mon sens pas au même niveau que les deux autres : c'est une "sous-page" spécialisée de Théorie de la complexité.

Pour ce qui est des noms, je pense que la page Analyse de la complexité des algorithmes ne prête pas trop à confusion. Par contre, c'est pour l'autre page qu'on est embêtés (et ça depuis longtemps étant donné les discussions à ce sujet qui remontent à... 2005 !). En fait le problème vien "tout simplement" du fait que ce domaine porte en anglais le nom de "Computational Complexity Theory" et que ce nom n'a pas de bonne traduction en français. Les gens du domane parlent de "Théorie de la complexité" ou de "Theorie de la complexité algorithmique" mais comme il a été dit, cela porte à confusion hors du domaine, donc dnas une encyclopédie. Je n'ai pas encore de bonne idée pour l'appellation. Ce que je propose de manière pratique est que cette page serve à la "Théorie de la complexité" et qu'une nouvelle page soit créée pour "Analyse des algorithmes". De manière pragmatique, le plus simple est sans doute de créer cette nouvelle page sans changer celle-ci, et qu'une fois que la nouvelle page est écrite et stabilisée, on enlève un peu de celle-là ce qui fait doublon, puis qu'on la complète (avec la complexité quantique, etc...).

Qu'en pensez-vous ? Grob (d) 20 avril 2011 à 01:38 (CEST)

Je suis d'accord qu'il est nécessaire de rediscuter du découpage et du périmètre de cet article. Tu dis qu'il faudrait s'inspirer de WP:en (ce en quoi je suis tout à fait d'accord), mais à quel article WP:en correspondrait Analyse de la complexité des algorithmes : en:Analysis of algorithms ? C'est juste pour avoir les idées claires.

Oui tout à fait, c'est de cette page que je parlais.

Sur le nom de cet article, tu n'as pas dit en quoi Théorie de la complexité des algorithmes ne convient pas. J'avais renommé l'article ainsi naguère, pour éviter la confusion avec d'autres théories traitant de la complexité, et c'est une traduction de "Computational Complexity Theory" utilisée régulièrement par Jean-Paul Delahaye dans ses articles et ouvrages. "Théorie de la complexité algorithmique" est aussi utilisée pour désigner ce domaine, c'est vrai, mais il y a malheureusement une confusion possible avec un domaine de la théorie algorithmique de l'information, la "complexité algorithmique" étant un nom souvent donné à la complexité de Kolmogorov. Mais j'ai l'impression qu'il n'y a pas de solution idéale, et que si on s'accorde pour dire que "théorie de la complexité des algorithmes" est trop peu usité, il faudrait renommer cette page, mais "théorie de la complexité" (le titre originel de l'article avant son renommage !) me parait le plus mauvais choix étant donné les multiples "théories de la complexité" qui existent, en passant par celle d'Edgar Morin ! Ou alors faire une page d'homonymie "Théorie de la complexité" avec cet article nommé "Théorie de la complexité (algorithmie)" ?

A l'époque, je n'avais pas eu beaucoup d'interlocuteurs pour parler de tout cela, et je suis content de voir que ce sujet suscite de nouveau de l'intérêt. Cordialement --Jean-Christophe BENOIST (d) 20 avril 2011 à 09:31 (CEST)

Mon problème avec ce nom est le suivant : quand on parle de "Théorie de la complexité des algorithmes", on met l'accent sur "algorithmes" alors que comme je le disais précédemment, l'objet d'étude dans ce domaine n'est pas vraiment l'algorithme, mais plutôt le modèle de calcul. Autrement dit, ce domaine a pour but d'étudier des "problèmes" de nature algorithmique, et non des "algorithmes". Ou pour paraphraser Bruno Poizat (dans Les Petits Cailloux), on étudie l'algorithmique (ou "algorithmie" comme il dit) et non les algorithmes. C'est à mon sens ce qui pousse les gens à parler d'analyse de la complexité des algorithmes dans cette page. "Théorie de la complexité des algorithmes" fait à mon sens pensé qu'on va étudier la complexité de certains algorithmes alors qu'on parle plutôt de l'objet abstrait "algorithme" et pas d'algorithmes spécifiques.

Maintenant pour trouver un nom correct... c'est pas facile ! Effectivement, Théorie de la complexité ne va pas, et au passage je suis d'accord sur le principe d'une page d'homonymie portant ce nom (quelque soit le nom qu'on donne à la page dont on parle ici) puisque des gens peuvent chercher "Théorie de la complexité" sans savoir que ça peut parler de plein de choses différentes. Personnellement, ma préférence va à "Théorie de la complexité algorithmique", et je pense que le problème de confusion avec la "Théorie algorithmique de l'information" peut être réglée par des bandeaux appropriés en début d'articles. Surtout qu'on parle d'un côté de "complexité" et de l'autre d'"information" donc ça sépare relativement bien les domaines. Une autre possibilité qui est plus rarement rencontrée mais peut-être plus fidèle au nom en anglais est Théorie de la complexité du calcul, mais ce n'est peut-être pas très heureux comme formulation. Enfin, ta proposition de Théorie de la complexité (algorithmie) me convient. Je note simplement que dans les discussions précédentes, certains voulaient éviter les parenthèses... Pour tous les noms proposés, enlever le "Théorie de" en début de nom peut alléger, sans que le titre devienne moins clair.

Une petite note : actuellement, Théorie de la complexité algorithmique redirige vers Théorie algorithmique de l'information ce qui me semble une bien mauvaise chose, pour deux raisons. Déjà, il me semble rare qu'on parle de "Complexité algorithmique" pour "Complexité de Kolmogorov" (ou tout autre appellation équivalente) , et d'autre part on utilise souvent ce terme pour "Computational Complexity". Peut-être qu'il faudrait rediriger cette page vers Complexité algorithmique, ce qui serait plus logique.

Cordialement, Grob (d) 21 avril 2011 à 15:56 (CEST)

C'est une discussion intéressante. D'abord, je pense qu'il est nécessaire de refaire une "opération sources", pour rebalayer les terminologies française en vigueur. Une source qui me parait assez représentative est [1] où "complexité algorithmique" et "complexité des algorithmes" est utilisé assez indifféremment. En revanche, cette source sépare nettement "complexité algorithmique (ou des algorithmes)" ( O(n) O(n²) etc.. ) et "complexité des problèmes" (P, NP etc..).

Je suis d'accord avec toi que "théorie de la complexité des algorithmes" porte trop l'attention sur les algorithmes, mais on pourrait presque en dire autant de "complexité algorithmique". Est-ce qu'il ne faudrait pas aller jusqu'au bout de la logique, et nommer cet article comme dans la source que je viens de citer (et d'autres comme [2] ou [3]) Complexité des problèmes, si le sujet de cet article est bien (mais nous sommes d'accord je crois) : P, NP etc.. et leur rapports.

Donc, un autre article serait consacré à la complexité algorithmique/des algorithmes. Je ne pense pas qu'il serait l'équivalent de en:Analysis of algorithms mais plus de en:Time complexity, car il parait nécessaire de parler dans cet article de la hiérarchie des complexités des algorithmes (logarithmique, polynomial, sub-exponentiel, exponentiel etc..) qui n'est pas vraiment décrite dans en:Analysis of algorithms.

Mais je continue de balayer les sources. Codialement --Jean-Christophe BENOIST (d) 21 avril 2011 à 17:04 (CEST)

PS : en effet, je suis d'accord laisser tomber la confusion possible complexité algorithmique/complexité de Kolmogorov. Elle peut exister, mais elle est effectivement mineure. --Jean-Christophe BENOIST (d) 21 avril 2011 à 17:06 (CEST)

Je mets un peu de temps à répondre car je n'avais pas trop de temps ces derniers jours. J'avais pas fait gaffe à en:Time complexity mais tu as raison, cet article correspond mieux à ce dont je parlais. Sinon, pour Complexité des problèmes, ça me gêne un peu parce que c'est trop général en un sens. On parle bien de "complexité algorithmique" dans le sens où c'est la complexité de résoudre un problème par un algorithme. Un entre-deux (lourdingue ?) serait Complexité algorithmique des problèmes.

Je suis d'accord sur le fait de balayer le plus de sources francophones possible. Je n'ai pas encore eu trop le temps de le faire mais vais essayer de m'y atteler. Pour être honnête cependant, je n'ai jamais vraiment trouvé de présentation qui me convenait entièrement, en français, de ce domaine. Mais ça existe peut-être ! Amicalement Grob (d) 8 mai 2011 à 01:01 (CEST)

C'est vrai que c'est pas évident parcequ'en français on parle souvent de Théorie de la complexité tout cour. Théorie de la complexité des problèmes me parait déja mieux adapté, mais il faudrait au moins dire dans l'intro: Théorie de la complexité des problèmes (souvent désigné par théorie de la complexité) ou un truc du genre. --Pparent (d) 21 juin 2012 à 10:03 (CEST)

Oui, je suis d'accord. D'ailleurs, dans l'intro de la source [2] plus haut, "théorie de la complexité" tout court désigne la théorie de la complexité des problèmes. Même si le titre "Théorie de la complexité des problèmes" n'est pas idéal (mais je pense qu'il doit en être proche), il faut aller de l'avant, on pourra toujours renommer (éventuellement) plus tard. --Jean-Christophe BENOIST (d) 21 juin 2012 à 11:07 (CEST)

bah si personne le fait, je finirai par le faire quand j'aurai le temps. Je sais pas encore trop comment renommer un article non-plus. --Pparent (d) 21 juin 2012 à 16:44 (CEST)

Mais oui ! N'hésites pas ! C'est comme cela que les choses avancent. Même si ce n'est pas parfait (mais je t'ai déjà vu travailler, j'ai confiance) cela pousse à réagir et à améliorer. Le "renommer" est bien caché entre l'étoile de suivi et la zone de recherche (petit triangle amenant un menu déroulant). Cordialement --Jean-Christophe BENOIST (d) 21 juin 2012 à 17:57 (CEST)

Confusion complexité Algorithme/problème

Bonjour,

Je trouve que cet article, n'est pas très clair, et mélange complexité des algorithmes et des problèmes.

En général lorsque l'on parle de "théorie de la complexité", il s'agit d'étudier la complexité des problèmes. Et le terme "complexité des algorithmes" est plus ou moins un abus de langage je crois. Wiki en utilise plutot "analysis of algorithms"

wiki (en): A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem.

Donc déja je pense que la première chose à faire et de changer le titre et l'intro. Qu'en pensez-vous? --Pparent (d) 20 juin 2012 à 12:03 (CEST)

ps: désolé je viens de voir la discussion d'au dessus, mais rien n'a été fait depuis.

Je pense qu'il y a consensus sur ce qu'il convient de faire. Il n'y a "plus qu'à". Le premier qui n'hésite pas aura raison ! --Jean-Christophe BENOIST (d) 20 juin 2012 à 12:26 (CEST)

Scission

Bonjour,

J'ai effectué le travail préparatoire à la scission discutée plus haut. Voici les deux articles:

• Théorie de la complexité (informatique théorique)
• Analyse de la complexité des algorithmes

S'il n'y a pas d'objections, j'effectuerai cette scission d'içi a quelques jours. Les articles pourront alors continuer à être améliorés normalement de manière indépendante. Vous pouvez bien sur corriger les éventuelles erreurs sur mes pages de brouillon.

--Pparent (d) 15 octobre 2012 à 17:27 (CEST)

Je n'ai pas d'obection sur la scission, par contre il faudra peut être discuter du nommage des article. Pour moi le premier pourrait s'appeler Théorie de la complexité (algorithmique) parce que Théorie de la complexité est une homonymie, bien qu'il faudrait vérifier pour la complexité de Kolmogorov si elle est bien désignée sous ce nom, et le deuxième complexité algorithmique tout simplement ... Voir « "Théorie de la complexité des problèmes" » (sur Google) n’est de fait pas très employée, voir carrément marginale comme terminologie, même si plus rigoureuse et plus précise dans l'absolu. — TomT0m ^[bla] 15 octobre 2012 à 17:40 (CEST)

Oui le terme employé est "théorie de la complexité" tout court et en pratique il n'y a pas d'autre terme réellement utilisé. Car à moins que l'on précise qu'on parle de la complexité de Kolmogorov, en général on fait référence à celle-ci. Il avait également été proposé "Théorie de la complexité des problèmes", qui semble un poil plus utilisé et plus simple, donc peut-être mieux. --Pparent (d) 15 octobre 2012 à 17:46 (CEST)

Donc, si je résume :

1) la partie "complexité" => A Théorie de la complexité (algorithmique) ou B Théorie de la complexité (algorithmie) ou C Théorie de la complexité des problèmes

2) la partie "algorithme" => Complexité algorithmique

Je serais assez pour 1B et 2. Comme je l'ai dit plus haut, je ne suis pas contre mettre Kolmogorov hors course. --Jean-Christophe BENOIST (d) 15 octobre 2012 à 17:57 (CEST)

Je suis plus pour la 1c car la complexité de kolmogorov n'est pas moins algorithmique (et qu'elle est tout de même importante), et en plus mettre problème dans le titre ça enlève tout de suite l’ambiguïté (qui a mené à son état actuel l'article) que l'on ne s'intéresse pas à la complexité d'un algorithme mais bien d'un problème. La numéro 2 "Complexité des algorithmes" à la limite.--Pparent (d) 15 octobre 2012 à 18:58 (CEST).--Pparent (d) 15 octobre 2012 à 18:58 (CEST)

Je suis pas trop pour ce titre parce que son usage est anecdotique, ça ne correspond pas trop au principe de moindre surprise (cf. Wikipedia:Conventions sur les titres). Dans tous les cas dans les articles il faudrait renvoyer vers les homonymies correspondantes. Tu as des sources pour le nommage "complexité algorithmique" de la complexité de Kolmogorov ? — TomT0m ^[bla] 15 octobre 2012 à 19:48 (CEST)

Non je n'ai pas de sources, mais je n'ai jamais édité cet article, donc il faudrait demander là-bas. Que diriez vous de quelque chose comme "Théorie de la Complexité (problèmes algorithmiques)". La parenthèse n’apparaîtrait que dans le nommage de la page mais pas dans l'intro. --Pparent (d) 15 octobre 2012 à 20:01 (CEST)

Ça m’a l’air beaucoup trop compliqué et inhabituel sur wp, c’est encore plus éloigné du principe de moindre surprise. La convention est de mettre entre parenthèse un domaine, comme les mathématiques ou l’algorithmi(qu)e, pas le domaine des problèmes algorithmiques qui est pour le moins bricolé . La subtilité sur les problèmes doit être expliquée dans l’article. — TomT0m ^[bla] 15 octobre 2012 à 20:15 (CEST)

Oui sauf que dans ce cas particulier on ne peut pas préciser le simple domaine puisque 2 théorie de la complexité font partie de ce domaine, et la deuxième selon l'article se fait également appeler "Théorie de la complexité algorithmique" ce titre redirige même vers la page. Je crois pas que l'on puisse s'en sortir sans faire un truc qui sort un peu de l'ordinaire. Et avoir une page "Théorie de la complexité algorithmique" et "Théorie de la complexité (algorithmique)" qui retournent vers 2 choses complètement différentes avouez que ce serait pour le moins confus.--Pparent (d) 15 octobre 2012 à 20:41 (CEST)

Sur algorithmie vs. algorithmique, j’ai l’impression d’avoir entendu beaucoup plus fréquemment algorithmique, et algorithmie redirige vers algorithmique, donc j’aurai tendance à privilégier la cohérence. Sans plus argumenter ni être formellement opposé à algorithmie. — TomT0m ^[bla] 15 octobre 2012 à 20:15 (CEST)

---

Tant que nous y sommes, un petit récapitulatif de l’existant :

• Complexité algorithmique et Théorie de la complexité en homonymie, actuellement redondant il me semble;
• complexité de Kolmogorov qui est une notion connexe mais très différente;
• complexité des algorithmes qui est une redirection;
• l’article général interdisciplinaire Complexité qui présente différentes notions de complexité dont celles qui nous intéressent;

(j’en oublie sûrement, n’hésitez pas à compléter la liste) Remarque au passage : l’article sur le sujet en anglais est un adq ... il y a surement de quoi s’inspirer dedans (voire de traduire sauvagement ). — TomT0m ^[bla] 15 octobre 2012 à 19:00 (CEST)

Je dois avouer que j'ai un peu perdu le fil de ce qui est proposé en terme de nommage. Je reste pour le moment sur le 1B (ou 1A)/2. En ce qui concerne la complexité de Kolmogorov, Delahaye la mentionne très volontiers en tant que "complexité algorithmique" (par exemple, l'entrée dans l'index du livre Information, Complexité et Hasard de "complexité algorithmique" redirige vers la complexité de Kolmogorov). Cependant, je pense qu'il n'y a guère que Delahaye pour le faire, et encore pas toujours de manière consistante. Donc, même si c'est moi qui suis à l'origine de la page d'homonymie (j'ai été nourri au Delahaye), je pense que cela apporte plus de confusion qu'autre chose, et cela complique (inutilement) la discussion sur le nommage de ces deux articles. Cordialement --Jean-Christophe BENOIST (d) 15 octobre 2012 à 21:21 (CEST)

Donc tu es pour "Théorie de la complexité (algorithmique)". Mais souhaite tu laisser la redirection de "Théorie de la complexité algorithmique" vers la Théorie algorithmique de l'information? Parce que dans ce cas là à 2 parenthèses près on se retrouve sur 2 pages qui non rien a voir, il y a un problème! Je restes sur ma dernière proposition " Théorie de la complexité (problèmes algorithmiques)", qui est certe un peu compliqué mais au moins le sujet de l'article est clair, on peut pas se tromper. --Pparent (d) 15 octobre 2012 à 22:02 (CEST)

Théorie de la complexité algorithmique devrait en fin de compte pointer sur Théorie de la complexité (algorithmique), dans la logique de séparer tout cela de la théorie algorithmique de l'information. Pas trop pour, honnêtement, " Théorie de la complexité (problèmes algorithmiques)". Je pense que ce qui est entre parenthèses doit représenter un vrai domaine dans lequel on pourrait trouver bcp d'articles. Or je pense que cet article, ainsi nommé, sera le seul à avoir ce domaine entre parenthèses. Et pourquoi pas tout simplement Théorie de la complexité (informatique théorique) ? --Jean-Christophe BENOIST (d) 15 octobre 2012 à 22:23 (CEST)

Oui c'est pas mal Théorie de la complexité (informatique théorique), en attendant de trouver mieux. --Pparent (d) 15 octobre 2012 à 22:37 (CEST)

La recherche Voir « "Théorie de la complexité algorithmique" kolmogorov » (sur Google) montre que non, Delahaye n’est pas tout seul à nommer les choses de cette manière. D'ailleurs ça doit être pour ça que Voir « "théorie de la complexité des algorithmes" -site:wikipedia.org » (sur Google) est un terme assez courant, dans des cours par exemple. — TomT0m ^[bla] 15 octobre 2012 à 23:02 (CEST)

Je crois que l'on viens de prouver que ce problème de nommage est au moins NP-Difficile! --Pparent (d) 15 octobre 2012 à 23:32 (CEST)

"Théorie de la complexité des algorithmes" convient également (pour la partie P, NP etc..), et Delahaye la nomme effectivement comme cela souvent. Je manque malheureusement de sources en français (à part Delahaye). Franchement, aucun des trois titres Théorie de la complexité (algorithmique), Théorie de la complexité (informatique théorique), ou Théorie de la complexité des algorithmes ne déshonorerait Wikipédia. Je pense que on converge avec les deux derniers. --Jean-Christophe BENOIST (d) 15 octobre 2012 à 23:54 (CEST)

Pour moi le dernier qui est l'actuel est trop trompeur, car laisse croire que l'on étudie la complexité d'un algorithme donnée (ce qui peut arriver), alors qu'il s'agit içi de la omplexité des problèmes. Le premier il y a le problème de confusion avec l'autre théorie que j'ai relevé tout à l'heure. Théorie de la complexité (informatique théorique) me parrait le plus acceptable. A voir ce qu'en dit TomT0m. --Pparent (d) 16 octobre 2012 à 00:05 (CEST)

Bon j'éffectue la scission, éventuellement le titre pourra être rechangé après, si nécessaire --Pparent (d) 16 octobre 2012 à 15:06 (CEST)

Théorie de la complexité (informatique théorique), Analyse de la complexité des algorithmes. Libre à vous d'améliorer ou de renommer. --Pparent (d) 16 octobre 2012 à 15:20 (CEST)

La complexité se calcule par rapport à la taille des données

Il me semble que dans le tableau des ordres de grandeur de complexité, il y a 2 exemples à changer : en effet, la complexité doit se calculer par rapport à la taille des données, en nombres de bits. Or dans l'exemple de la multiplication matricielle classique, le temps est en O(n^3) pour deux matrices de taille n x n. Les données sont donc de taille 2 n^2, ce qui fait que la complexité est en O(d^{3/2}), où d est la taille des données. Ce n'est donc pas une complexité cubique. De même, l'exemple pour 'quadratique' est 'le parcours d'un tableau' avec sans doute un tableau de taille n x n. Le parcours d'un tableau est donc en réalité de complexité linéaire O(d) = O(n^2). S'il y a accord sur ceci, il faut juste trouver d'autres exemples: le tri à bulles en O(d^2), la corrélation partielle en O(d^3) p.ex. Pyschobbens (discuter) 1 juin 2022 à 21:26 (CEST)