1

Dans le cadre d'un TP qui vise sur un petit utilitaire de crypto, il faut décrire la complexité des fonctions qu'on a codé. J'ai quelques cas précis qui me causent souci et comme certains ici ont fait des études poussées en info peut être que vous pourrez m'aider smile

1) J'ai une opération à l'intérieur de la boucle, nommément:
m = (m * m) mod p;
La première fois m sera très grand et l'opération de multiplication tournera au O(M^2) (M = bitsSignificatifs(m), donc en théorie on est en lb2(m) mais je mets de côté pour simplifier). Les fois subséquentes on tombe dans du O(P^2) puisque m < p.
A priori j'aurais tendance à borner en M^2 pour simplifier, mais si on rajoute:
m = m mod p;
Avant la boucle, alors le problème semble plus facile, car m >> p. Après je sais pas si c'est pertinent, j'aurais tendance à dire que non. Qu'en pensez-vous?

2) Mettons que j'ai une boucle qui s'exécute N fois, et dans laquelle j'ai des opérations prenant N itérations et d'autres prenant M. La complexité serait O(N*(N+M)). On peut exprimer ça comme ça? J'ai jamais vu nulle part ailleurs sorry
Y a pas une supposition raisonnable qui peut me permettre de retomber en O(N^2) pour simplifier?

Merci d'avance, je suis un peu paumé hehe
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

2

pas lu le 1), mais pour le 2), on tombe souvent sur ce genre de complexités quand on a des algos de graphes (n sommets, m arêtes), donc je ne trouve pas ça choquant. (mais si m < n, tu peux simplifier en O(n²), évidemment)
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

3

Ok merci. En fait je peux supposer que m < n sinon l'algo dégénère et donne la réponse immédiatement hehe

Pour le 1) j'arrive à une complexité de O(log(n)*(m2+n)). C'est moins courant ça non? grin
(il y a une boucle de log(n) opérations faisant des opérations de complexité m^2 et n)
Je me demande ce que je fais de faux sorry
avatar
Highway Runners, mon jeu de racing à la Outrun qu'il est sorti le 14 décembre 2016 ! N'hésitez pas à me soutenir :)

https://itunes.apple.com/us/app/highway-runners/id964932741

4

Perso j'ai toujours trouvé que la complexité était un concept assez bidon :

- c'est défini à un facteur multiplicatif près, donc un algo en O(n) peut très bien être plus lent qu'un algo en O(n²) par exemple. Tout ce que ça garantit, c'est que l'algo en O(n) sera plus rapide que l'autre pour n supérieur à une limite, mais ça ne donne pas la valeur de cette limite (elle peut être plus élevée que le n maximum dont on a besoin).

- c'est basé sur un concept abstrait, ça ne tient pas compte du "coût" réel des opérations : une multiplication est la plupart du temps bien plus lente qu'une addition, un transfert mémoire qu'un transfert entre registres, un accès mémoire hors cache qu'un accès en cache, etc. Ce sont des choses qui influent aussi beaucoup sur les performances.

- ça suppose que le temps d'exécution soit une fonction monotone croissante qui ne dépend que de n : y'a plein de cas où c'est faux, suffit que l'algo ait des branchements conditionnels ; comment classer un algorithme très rapide dans la plupart des cas et beaucoup plus lent dans 1 ou 2 cas "pathologiques" ?
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

5

- sauf que justement, ça sert
1) à prédire l'évolution quand n devient grand
2) savoir si on peut faire mieux, quand n devient grand
Typiquement, j'avais d'abord implémenté un algo en O(n²) (avec n de l'ordre de quelques milliers, il était plus rapide que l'algo en n), puis quand n a valu 200 000 000, j'ai préféré passer à un algo en O(n) grin

- non, c'est faux, quand tu fais des algos de multiplication rapide (Karatsuba, Toom-3, FFT, ...) tu comptes les multiplications, par exemple.

- parce que tu te contentes de la complexité dans le pire des cas : on sait également faire de la complexité en moyenne (mais c'est beaucoup plus compliqué, en général).

Accessoirement, quand tu montres qu'un problème est de complexité exponentielle, ou qu'il est NP-complet, alors tu peux abandonner ta solution exacte (si N devient grand, évidemment), quelque soit le temps que tu vas passer à optimiser tongue
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

6

Je ne dis pas que ça ne sert à rien hein, je dis que c'est trop simpliste à mon goût ^^

- Admettons. On ne me l'avait pas présenté comme çà.

- OK, alors là je blâme le prof d'info qui nous avait fait le cours là-dessus, il avait honteusement passé ça sous silence grin
Reste qu'il y a beaucoup de choses qui ne peuvent pas s'exprimer par un simple O(machin), on ne peut pas décider d'un algo sur ce seul critère.

- le pire des cas c'est bien quand tu dois faire du temps réel, par contre souvent c'est plutôt le temps d'exécution moyen qui importe.
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

7

- bah quand n est borné, la notation de Landau (les O et les o) n'a aucun sens. Déjà, en théorie on devrait utiliser la notation en Θ qui est plus précise (dire qu'un algo en O(n) est un algo en O(n²) est juste mais sa complexité est surestimée), et on devrait surtout mettre en-dessous un petit « n -> ∞ ». Son seul domaine de validité, c'est quand n devient grand.
- tu n'es pas obligé d'utiliser la notation en O, justement smile pour les multiplications rapides, on compte précisément le nombre d'opérations + et *, ça suffit à comparer les algos en présence.
- mais rien ne t'empêche de faire de la complexité en moyenne, hein hehe
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

8

j'ai quelques remarques à ajouter:

1-la complexité peut être exprimée en fonction de plusieurs paramètres d'entrée

par exemple (et cela a été dit au début de cette discussion), les algo sur les graphes ont généralement une complexité exprimé en terme de |V| (le nombre de sommets) et |E| (le nombre d'arêtes)

dans le cas des graphes simples, comme on sait que |E| = O(|V|^2), il arrive que l'on simplifie l'expression obtenue
mais je trouve plus intéressant de garder la complexité exprimée en fonction des deux paramètres car ça en dit plus sur le comportement de l'algo dans le cas de graphes peu denses ou bien dans le cas de multigraphes (si l'algo a encore un sens)

2-on peut compter les opérations que l'on veut. généralement on compte l'opération la plus coûteuse mais rien n'empêche de tout compter (ça fera juste des systèmes d'équations plus compliquées à résoudre...)
on peut aussi vouloir évaluer la complexité en mémoire plutôt que celle en temps

3-l'exemple archi-classique d'algo où l'on fait une étude de la complexité en moyenne est le tri rapide (quick sort)
la complexité en comparaisons dans le pire cas est O(n^2) alors qu'elle est O(n log(n)) en moyenne

9

SebRmv (./8) :
3-l'exemple archi-classique d'algo où l'on fait une étude de la complexité en moyenne est le tri rapide (quick sort)
la complexité en comparaisons dans le pire cas est O(n^2) alors qu'elle est O(n log(n)) en moyenne

Y a-t-il un seul autre algo dont on étudie la complexité en moyenne ? cheeky

Bon, j'exagère un peu, mais c'est vrai que je n'ai aucun souvenir d'une étude en moyenne pour autre chose...
avatar
<<< Kernel Extremis©®™ >>> et Inventeur de la différence administratif/judiciaire ! (©Yoshi Noir)

<Vertyos> un poil plus mais elle suce bien quand même la mienne ^^
<Sabrina`> tinkiete flan c juste qu'ils sont jaloux que je te trouve aussi appétissant

10

j'imagine les algo probabilistes

sinon, il a aussi la notion de complexité amortie qui est intéressante
l'exemple classique ici est celui des tableaux qui se redimensionnent dynamiquement

11

Zerosquare > ./6 « si on considère la complexité de façon simpliste, c'est simpliste »
./4 « si on utilise une représentation simpliste de la complexité dans des cas complexes où c'est pas approprié, c'est bidon » et « la complexité asymptotique n'a aucun intérêt si on s'intéresse pas aux grandes valeurs de n »

non, sans blague tongue
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#

12

Comme je l'ai déjà dit, le blâme en revient au prof d'info qui nous avait présenté la complexité de façon tronquée, je ne connaissais pas les compléments que Flanker a donnés.

Et puis un up de plus d'un mois pour se foutre de ma gueule, c'est mesquin tongue
avatar
Zeroblog

« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » — Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » — GT Turbo

13

Tiens j'avais pas vu le up, désolé confus (en termes de position je n'ai uppé le topic que d'un cran, ça ne m'est pas venu à l'idée qu'il puisse être vieux cheeky)
avatar
« Le bonheur, c'est une carte de bibliothèque ! » — The gostak distims the doshes.
Membrane fondatrice de la confrérie des artistes flous.
L'univers est-il un dodécaèdre de Poincaré ?
(``·\ powaaaaaaaaa ! #love#