Discussion :

[deeal]

bonjour
je voudrais calculer la complexite de mon algorithme

qui est du style

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
   while (i<=N) // N connu ce n'est pas le probleme
    {
       // quelque instruction donc O(1)
        while (Var=True) // c'est la mon probleme
         {
 
 
         }
 
     }

donc le probleme c'est que je ne sais pas quand mon algorithme positionne la variable Var a false pour sortir de la boucle for
si vous pouvez m'aider ou vous avez des liens
Merci
PS: je galere

[gangsoleil]

Bonjour,

Tu as une boucle infinie, qui est brisée selon une condition que tu ne précises pas ici. N'étant pas devin, je ne sais ce que c'est, mais bon imaginons que ce soit une fin de fichier :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
while (i<=N) // N connu ce n'est pas le probleme
    {
       // quelque instruction donc O(1)
        while (Var=True) // c'est la mon probleme
         {
              // lire dans fichier
              si fichier = fini
                   quitter boucle
              sinon
                 algo en O(1)
         }
 
     }

Dans ce cas, la complexité est dépendante de la taille de ton fichier, et n'est plus si complexe à calculer.

[deeal]

desole mais voila ce que je fais
c'est un graphe et je dois chercher les N plus court chemin
le probleme c'est de maximiser le cout du chemin

donc la condition d'arret c'est d'arriver a l'etat final de mon graphe
mais on ne connait pas la longeur du chemin
tu veux plus d'explication??? je suis la

donc ça doit etre une fonction avec trois varaibles

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
F(N,M,K)  // M :nombres d'arretes ; N:nombres de noeuds;K: nombres de chemin

[deeal]

Daviv eppstein

We find the k shortest paths (allowing cycles) connecting a given pair of vertices in a digraph,
in time O(m+nlogn+k)

donc il trouve les K premiers plus courts chemins (avec cycles autorisés)
dans un graphe orienté
mais c'est pas le meme algorithme que j'utilise,
moi j'utilise le fameux Branch And Boudn "separation evaluation"

http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf

[deeal]

ça me rassure de voir des truc comme cela

Il existe même toute une classe de problèmes extrêmement difficiles à résoudre pour lesquels on ne sait même pas si leur solution optimale est polynomiale ou non. En fait, on ne sait les résoudre qu'avec des algorithmes de complexité exponentielle (si vous ne savez pas ce que cela signifie, en un mot, cela veut dire que c'est une véritable catastrophe). Cependant, cela ne veut pas forcément dire qu'on ne peut pas faire mieux, mais tout

Cours C/C++

je ne suis pas con alors