Salut,

Si je m'en souviens bien, on pouvait utiliser des sortes d'invariant d'un algorithmes dans des nested for loops (imaginons O(n^2)) pour pourvoir le simplifier en un seul boucle for ( O(n)). Mais je ne m'en souviens pas très bien. C'était quelque chose que j'avais vu une fois en cours. J'ai essayé de chercher sur le net mais je n'y arrive pas. Est-ce que quelqu'un sait de quoi je pourrais parler et qui pourrait m'aider?

Alors je dois avouer que ça date un peu donc je ne m'en souviens pas forcément super bien ce que tu cherche se nomme théorie de la terminaison et de la complexité.

L'invariant c'est un propriété qui ne change pas à chaque itération d'une boucle et permet de démontrer la terminaison d'un algorithme.

Ce n'est donc pas ce que tu cherche.

Ce que tu cherche c'est le dénominateur commun des deux boucles. L'intérêt est comme tu l'as dis est de diminuer la complexité de temps des algorithmes naïfs.

J'ai trouvé un site qui résume plutôt bien le tout sans rentrer dans de la théorie algorithmique pompeuse:
https://librecours.net/module/js/js03/pres/co/optimisation.html?mode=html#:~:text=Complexit%C3%A9%20en%20temps&text=Elle%20donne%20un%20ordre%20d,de%20vue%20de%20l'utilisateur.

Le 18 janvier 2023 à 08:17:47 :
Alors je dois avouer que ça date un peu donc je ne m'en souviens pas forcément super bien ce que tu cherche se nomme théorie de la terminaison et de la complexité.

L'invariant c'est un propriété qui ne change pas à chaque itération d'une boucle et permet de démontrer la terminaison d'un algorithme.

Ce n'est donc pas ce que tu cherche.

Ce que tu cherche c'est le dénominateur commun des deux boucles. L'intérêt est comme tu l'as dis est de diminuer la complexité de temps des algorithmes naïfs.

J'ai trouvé un site qui résume plutôt bien le tout sans rentrer dans de la théorie algorithmique pompeuse:
https://librecours.net/module/js/js03/pres/co/optimisation.html?mode=html#:~:text=Complexit%C3%A9%20en%20temps&text=Elle%20donne%20un%20ordre%20d,de%20vue%20de%20l'utilisateur.

Merci pour la réponse. J'ai pensé à ça aussi sauf que ce que j'avais particulièrement en-tête par contre c'était un peu comme le problème de "trapped rain water" mais avec le nom "tea cup". En gros, pour le "tea cup", dans un array de nombre naturel, on doit trouver la "vallée" la plus longue. Exemple : 7,4,3,3,4,6 est une vallée à cause de la monté et de la descente. Je pense qu'on construit d'abord une boucle n^2 de façon naïve, on remarque un invariant et on l'utilise pour le simplifier (ATTENTION: je ne demande pas qu'on me donne la solution à ce problème).
Ce que je veux savoir, pour ceux qui ont fait le problème de dessus, si c'est bien juste une histoire de trouver un "dénominateur commun aux deux boucles" ou bien il y a bien une technique particulière où on utilise un invariant?

Maintenant que j'y pense, l'idée serait de trouver un invariant qui reste vrai à chaque itération et d'utiliser cet invariant pour nous donner la solution et qu'on a ainsi un algo (une boucle plutôt) en O(n)...

Merci pour les réponses si vous en avez d'autres

Je pense qu'on construit d'abord une boucle n^2 de façon naïve

C'est quoi ta boucle naïve ? Pour moi ça se fait directement en une passe, je vois pas trop ce que pourrait apporter des boucles imbriquées pour ce problème

En effet, on peut utiliser l'analyse de boucle pour trouver une maniere plus efficace de faire les boucles. Imagine un truc comme ca:

for (int i=0; i<n; ++i)  {
  int mysum = 0;
  for (int j=0; j<i; ++j) {
   mysum +=i;
  }
 print (mysum); 
}

Quand tu fais l'analyse, tu verra que mysum vaut i(i+2)/2 a la fin de la boucle j et donc tu peux couper la boucle entierement.

Peut être c'est intéressant de se donner d'abord des exemples d'entrée/sorties et analyser la relation mathématique qu'il y a entre chaque E/S au lieu de simuler une boucle for ?

Ceci dit, simuler une boucle for c'est une approche assez bas niveau et impérative. Si on essayer de dire ce qu'on veut faire au lieu de comment (utiliser un ordinateur pour) faire ça peut sembler moins casser-tête ?

Le 22 janvier 2023 à 16:51:38 Oberginee a écrit :
Peut être c'est intéressant de se donner d'abord des exemples d'entrée/sorties et analyser la relation mathématique qu'il y a entre chaque E/S au lieu de simuler une boucle for ?

Ceci dit, simuler une boucle for c'est une approche assez bas niveau et impérative. Si on essayer de dire ce qu'on veut faire au lieu de comment (utiliser un ordinateur pour) faire ça peut sembler moins casser-tête ?

La réponse a déjà était plus ou moins donnée et trouvée au-dessus et j'avoue aussi retrouvé mes cours en pdf par après. Merci quand même d'avoir pris le temps de répondre par contre.

Pour ceux qui viendront lire ce topic, l'idée est comme suit. Imaginons que vous n'arrivez pas à faire un algorithme simple (que ce soit parce que vous n'y trouvez tout simplement pas ou bien que vous commencez à être fatigué), l'idée c'est que si vous avez un algorithme naif (donc comme j'ai dit, vous êtes n'avez pas réussis à trouver une version simplifié ou bien parce que vous êtes fatigués après 2 semaines de codes), vous l'implémentez et vous l'analyser en essayant de trouver un invariant quand vous sortez de la boucle imbriqué. L'astuce serait maintenant d'utiliser cet invariant (avec potentiellement une variable auxiliaire (souvent le cas)) pour implémenter un algorithme plus simple (avec une boucle imbriqué en moins).

Quand je disais fatigué, je ne parlais pas de quand il fait tard au soir et que vous vouliez dormir mais que vous codez depuis longtemps et que votre à besoin de se reposer (un peu comme ceux qui font de la muscu 5 fois par semaine et qui ne permettent pas à leur corps de se reposer). Donc en gros, fatigué dans le sens où vous ne vous en rendez pas compte.

Le topic a été resolu mais je ne l'ai pas bloqué au cas où d'autres gens voulaient poser des questions concernant ce sujet.