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
