Complexité exponentiation modulaire - Page 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

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 lb²(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
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é

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)

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

Pour le 1) j'arrive à une complexité de O(log(n)*(m²+n)). C'est moins courant ça non?
(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

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" ?

- 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)

- 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

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
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.

- 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 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

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

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 ?

Bon, j'exagère un peu, mais c'est vrai que je n'ai aucun souvenir d'une étude en moyenne pour autre chose...

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

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

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

Tiens j'avais pas vu le up, désolé (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 )