13-02-2013, 05:45 PM
Tout ne sera pas n², mais il suffit qu'un algo soit n² pour que les centaines d'algo en O(n) deviennent négligeables (10.000² >> k*10.000 même pour k=100).
Des algos O(n²), il risque d'en avoir: un homme cherche une femme (ou inversement), est-ce que deux personnes se croisent dans la rue, est-ce que deux personnes travaillent ensemble (et ne peuvent pas s'encadrer donc, elles travaillent mal) etc. Bref, il y a plein de cas où il risque de gérer des couples d'individus, ce qui fera un nombre de possibilités à traiter de l'ordre de n².
Peut-être n'en aura-t-il pas, ok, mais en ce cas, on retombera sur les pots précédents, qui disent "fait pas une simulation de chaque bonhomme individuellement (car si y'a pas de n², y'a pas de couple, donc on traite individuellement) mais une simulation de groupe".
Des algos O(n²), il risque d'en avoir: un homme cherche une femme (ou inversement), est-ce que deux personnes se croisent dans la rue, est-ce que deux personnes travaillent ensemble (et ne peuvent pas s'encadrer donc, elles travaillent mal) etc. Bref, il y a plein de cas où il risque de gérer des couples d'individus, ce qui fera un nombre de possibilités à traiter de l'ordre de n².
Peut-être n'en aura-t-il pas, ok, mais en ce cas, on retombera sur les pots précédents, qui disent "fait pas une simulation de chaque bonhomme individuellement (car si y'a pas de n², y'a pas de couple, donc on traite individuellement) mais une simulation de groupe".