TROIS ALGORITHMES POUR LA SUITE DE FIBONACCI
Cacophrene
Messages postés
251
Date d'inscription
lundi 29 mars 2004
Statut
Membre
Dernière intervention
4 mars 2008
-
9 juil. 2006 à 17:13
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 - 16 mars 2012 à 05:44
Renfield Messages postés 17287 Date d'inscription mercredi 2 janvier 2002 Statut Modérateur Dernière intervention 27 septembre 2021 - 16 mars 2012 à 05:44
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/38496-trois-algorithmes-pour-la-suite-de-fibonacci
https://codes-sources.commentcamarche.net/source/38496-trois-algorithmes-pour-la-suite-de-fibonacci
16 mars 2012 à 05:44
15 mars 2012 à 20:43
16 nov. 2006 à 08:26
Private Function ReyFibonacci(ByVal n As Long) As Long
Dim n1 As Long
Dim n2 As Long
Dim i As Long
If n > 0 Then
If n <= 2 Then
ReyFibonacci = 1
Else
n1 = 1
n2 = 1
For i = 3 To n - 1
If i And 1 Then
n1 = n1 + n2
Else
n2 = n1 + n2
End If
Next i
ReyFibonacci = n1 + n2
End If
End If
End Function
Je voulais savoir ce que cet algorithme vallait, et je m'apercoit qu'il est plutôt rapide ^^
29 juil. 2006 à 07:44
Un problème de matériel... ce n'est pas drôle ça ! Au pire, il est toujours possible de se rabattre sur GetTickCount. On obtiendra des mesures moins précises, mais faute de mieux c'est encore raisonnable.
Cordialement,
Cacophrène
28 juil. 2006 à 18:01
"Problem's been solved. I found a hot-fix for Xp that fixes the QueryPerformanceCounter, so things have returned to normal once more. http://support.microsoft.com/?id=896256 for more info on that if you're interested."
Cela résoud il aussi votre problème?
28 juil. 2006 à 17:58
Non ce n'est pas la version de Windows, car cette API fonctionne bien avec Windows XP Edition Familiale (SP1 & SP2). En revanche, ca pourrait être lié au hardware de la machine (cf. http://channel9.msdn.com/ShowPost.aspx?PostID=156175)
De plus, MSDN précise bien dans la doc de cette API : "... bla bla SI VOTRE SYSTEME EST EQUIPE DUN COMPTEUR HAUTE PERFORMANCES bla bla bla ..."
La machine sur laquelle tu as un souci serait elle un Atlhon?
28 juil. 2006 à 16:32
28 juil. 2006 à 08:45
@Patrice:
Je ne vois pas comment tu peux obtenir des résultats négatifs. Je n'ai jamais été confronté à ce problème. Si tu as d'autres infos, je suis preneur.
@us_30:
D'accord pour le côté pratique. On tire profit des types (de leur précision) et des conversions. Heureux bricolage, diront certains.
Cordialement,
Cacophrène
27 juil. 2006 à 22:51
Cacophrène tu as raison, la fonction puissance cache une complexité, donc on ne pas dire que le calcul d'une formule est constant, du moins en théorie... car en pratique... je suis moins sûr... En effet, il ne t'a pas échappé que les calculs sont effectués seulement avec des chiffres significatifs, le reste étant coupé sans jamais être calculé (ou du moins une partie du reste). Par conséquent, un calcul d'une puissance (ou autre chose) même avec des nombres importants, met "quasiment" le même temps qu'une autre valeur... C'est la raison pour laquelle que j'ai écris : "finalement constante" ... IL est vrai que j'aurais dû mieux préciser ma remarque...
Amicalement,
Us.
27 juil. 2006 à 15:59
27 juil. 2006 à 15:01
Après quelques recherches sur le net, voici quelques informations relatives au type de programme proposé par Patrice99. Il s'agit d'une méthode de programmation dynamique que les anglais nomment memoization (mot formé à partir du mot latin memorandum qui signifie "chose à retenir").
Cordialement,
Cacophrène
24 juil. 2006 à 19:33
La complexité est plus faible 1. pour une raison intuitive (l'algorithme est sensiblement plus rapide que son équivalent sans sauvegarde des résultats intermédiaires) et 2. pour une raison logique (le nombre d'opérations élémentaires (additions surtout) a fortement diminué puisque nous ne refaisons pas les calculs déjà effectués). En fait, il ne reste plus qu'à mettre un nom sur cette complexité. Avis aux amateurs :-D
Cordialement,
Cacophrène
24 juil. 2006 à 16:13
24 juil. 2006 à 13:04
Merci pour ton code Patrice99. Je m'en suis inspiré (sans le suivre vraiment à la lettre, car ma compréhension du C++ n'est que partielle... et plutôt par déduction/analogie que par pratique) pour rédiger un algorithme 1' faisant suite au premier dont il dérive. Evidemment, pour les performances, il n'y aucune comparaison possible.
Cordialement,
Cacophrène
23 juil. 2006 à 13:20
23 juil. 2006 à 13:01
N'allons pas trop vite. Ecrire que l'application directe de la formule de Binet (message de us_30 ci-dessus, en rapport avec une source déjà postée sur VBFrance) donne une complexité constante, c'est séduisant, certes, mais faux. N'oublions pas que l'écriture "^ N" cache un calcul de puissance, donc au moins une complexité logarithmique (si la fonction interne de VB est une exponentiation rapide)... car la "puissance" (ou exponentiation pour faire jargonneux) n'est pas une opération élémentaire. Si Binet donnait Fibonacci en un nombre constant d'opérations élémentaires... tous les algorithmes seraient idiots. Pourquoi ? Parce que cela voudrait dire qu'il suffirait de demander Binet(10^(10^10)) pour avoir IMMEDIATEMENT Fibo(10^(10^10)) ! Prudence donc.
Cordialement,
Cacophrène
22 juil. 2006 à 15:35
euh... Patrice99, je ne comprend trop bien où tu veux en venir. Bon, déjà le C++ c'est pas trop ma tasse de thé... En plus, je crois que l'algo correspond à un de ceux présentés par Cacophrène... et la discussion se portait sur la commplexité... donc, je ne vois pas ? (remarque amicale)...
Ceci dit, on peut codé une façon directe de calculer le nombre de Fibonacci, présenté à http://www.vbfrance.com/codes/FIBONACCI-SUITE_36926.aspx
que j'ai adapté ainsi (à titre de complément) :
=
Function Fibonacci(ByVal N As Long) As Double
If N < 1 Then Exit Function
Fibonacci = Int(((1 + Sqr(5)) / 2) ^ N / Sqr(5) + 0.5)
End Function
=
et dont la complexité est finalement constante puisque c'est une formule. Le résultat renvoyé est exact grâce à l'arrondi effectué. Ce qui serait intéressant c'est de disposer de formule similaire pour d'autres suite... (évidemment)... mais c'est loin d'être évident, c'est sur... mais là je fais une auto-référence à ma question lors de ma dernière intervention...
Amicalement,
Us.
22 juil. 2006 à 14:22
www.microsoft.com/downloads/details.aspx?familyid=86ce6052-d7f4-4aeb-9b7a-94635beebdda&displaylang=en
// Still recursive, but remembers previous results - much faster.
static int Memo_Fibo(int i)
{
int result;
if (!fibo_memo.FindResult(i, out result))
{
if (i <= 1)
result = i;
else
result = Memo_Fibo(i-1) + Memo_Fibo(i-2);
}
// This call leaks memory,
// because it always adds to the list.
fibo_memo.Enter(i, result);
return result;
}
You can simply look in a cache to determine whether you already computed Fibo with this argument. If so, you simply return the previous result; otherwise, you compute it. And of course, if you compute it, you enter it into the cache.
The following example shows how the cache works. It is nothing fancy ? a linear list, with ways to search and enter new information.
// List to remember association of previous arguments and results.
class ListEntry
{
int argument;
int result;
ListEntry next;
public ListEntry(int argument, int result, ListEntry next)
{
this.argument = argument;
this.result = result;
this.next = next;
}
public bool FindResult(int argument, out int result)
{
if (this.argument == argument)
{
result = this.result;
return true;
}
else if (next != null)
{
return next.FindResult(argument, out result);
}
else
{
result = 0;
return false;
}
}
}
ListEntry memoList;
public Memo()
{
memoList = null;
}
void Enter(int argument, int result)
{
memoList = new ListEntry(argument, result, memoList);
}
bool FindResult(int argument, out int result)
{
if (memoList != null)
{
return memoList.FindResult(argument, out result);
}
else
{
result = 0;
return false;
}
}
12 juil. 2006 à 09:17
Les complexités se classent en plusieurs catégories dont voici les principales :
Logarithmique
Linéaire
Quasi-linéaire
Polynomiale (dont quadratique, cubique, etc...)
Exponentielle
Factorielle (éventuellement)
Il existe aussi de très nombreuses "sous-catégories". De plus, certains algorithmes ne rentrent pas tout à fait dans l'une quelconque de ces catégories.
Les problèmes abordés, eux, peuvent eux-aussi être classés en plusieurs catégories (et c'est une activité pour le moins difficile !). Cela nous mène au lien donné par Patrice99. Pour citer quelques exemples, la résolution des Sudoku est un problème NP-complet, de même que les cryptarithmes ou la recherche d'une solution au Master Mind. En général, pour de tels problèmes, on utilise des règles heuristiques qui permettent de limiter les choix effectués par l'ordinateur pour accroître la vitesse de résolution.
On peut voir la même chose avec le parcours de toutes les cases d'un échiquier par un cavalier. Si l'on s'amuse à utiliser la méthode ordinaire (le rebroussement ou backtracking), on pourra attendre très longtemps... mais on doit théoriquement obtenir TOUTES les solutions. Si on utilise la règle heuristique de Warnsdorff, qui consiste à privilégier les cases situées au bord de l'échiquier, on peut espérer obtenir UNE solution avec une complexité grosso modo linéaire.
Pour tous ces exemples, on ne sait pas si l'on peut "mieux" faire (en particulier, la règle de Warnsdorff n'est plus applicable pour de très grands échiquiers où elle donne des parcours incomplets). C'est peut-être mieux ainsi : il y a toujours l'espoir de trouver un meilleur algorithme ou une règle conduisant à un plus grand accroissement des performances.
Cordialement,
Cacophrène
12 juil. 2006 à 08:49
Je crois que non, pas d'une manière générale : en fait j'ai cru comprendre qu'on classe les problèmes dans 4 catégories principales, suite à une analyse au cas par cas :
http://patrice.dargenton.free.fr/ia/vbbrainbox/index.html#_Toc39118564
11 juil. 2006 à 22:54
Que des bonnes remarques... Je suis en tout point en accord avec la réponse de Jean_Marc_N2 à la question de Patrice99.
IL serait très ambitieux d'inventer un nouveau concept, voir un poil prétentieux... mais bon, il est certain qu'on ne peut être qu'à demi satisfait de la mesure de la complexité. Pourquoi pas avancer des idées...
Une question un peu générale que je me pose, c'est de savoir s'il existe une limite théorique à la mesure de la complexité pour résoudre un problème donné. JE m'explique.
La complexité donne une mesure pour un algorithme donné. Or, on peut fort bien trouver des algorithmes des complexités différentes pour un même problème. Par exemple ici, pour le même calcul du nombre Fibonacci, on a 3 algorithmes différents avec 3 mesures de complexités. Existe-t-il donc un moyen de savoir que la complexité ne peut être inférieure à une certaine borne ?... sans pour autant connaître l'algorithme. Dure question... -:);
Amicalement,
Us.
11 juil. 2006 à 14:04
11 juil. 2006 à 12:34
Exact ! De même qu'il existe des algorithmes dont la complexité est indépendante de la distribution des données (par exemple le tri fusion est toujours de complexité logarithmique), il en existe dont celle-ci peut être largement modifiée par des distributions convenablement choisies. Fort heureusement, ici, nous ne manipulons pas de données (pour les trier par exemple). Ainsi sommes-nous certains d'avoir une et une seule complexité.
On pourrait d'ailleurs ajouter qu'à côté de la complexité temporelle existe une complexité spatiale. On peut trouver de très bons algorithmes qui, rédigés sous une forme plutôt qu'une autre (par exemple, sous forme récursive plutôt qu'itérative), demandent une mémoire considérable. Je pense par exemple à l'algorithme de Cooley-Tukey pour les transformées de Fourier rapides (FTT). Programmé sous forme récursive, cet algorithme possède une complexité spatiale plus importante que son équivalent itératif... pour une même complexité temporelle en O(n * log n). Prudence donc...
@Patrice99 : La notation de Landau pose un problème qu'il est important de noter. Supposons que, pour réaliser une tâche quelconque, nous disposions de deux algorithmes, l'un en O(n^2) et l'autre en O(n^3). Tout le monde de conclure : "un algorithme quadratique est plus rapide qu'un algorithme cubique". Certes, c'est "presque toujours" vrai. Mais il ne faut pas oublier que ce n'est rigoureusement vrai que pour n très grand. Si, à l'extrême, O(n^2) cache un 10^10 * n^2 alors que O(n^3) cache un 2 * n^3, il y a fort à parier que pour des valeurs moyennes de n, l'algorithme ayant la plus grande complexité soit pourtant le plus rapide... La notation de Landau cache parfois de traîtres constantes. Par chance, ce "parfois" est "très rare", et ces situations aussi !
Cordialement,
Cacophrène
11 juil. 2006 à 10:18
Par exemple les algorithmes de tris: QuickSort (complexité moyennee n N.logN) devient très mauvais quand N est raisonnablement petit ET que le tableau est "presque" trié (Voir D.Knuth, The Art of Computer Programming, Volume 3 "Sorting and Searching", Chapitre 5.2.2). Dans ce cas, un tri à bulle (complexité en N^2) devient meilleur car pour ce cas particulier, la complexité tend à devenir plus ou moins O(n) alorq que QuickSort "devient" en O(n^2).
Il y a pas mal d'exemples de ce type. On peut aussi citer l'utilisation des tables de hachage. Elles garantissent en général un accès en O(1), mais dans certains cas dégénérés introduisant des collisions, l'emploi d'une recherche dichotomique (en N.Log N) est plus efficace.
La mesure de la complexité est un art difficile car un algorithme n'a pas toujours UNE complexité mais DES complexités (meilleur cas, cas moyen, pire cas, cas particuliers, etc.).
11 juil. 2006 à 09:15
Je suis sceptique : j'aimerais bien avoir un cas où un algo plus complexe est plus rapide ? (sauf évidemment pour le cas où il existerait une carte matériel accélératrice dans un cas et pas dans l'autre). Car c'est bien pour ça qu'on a inventé la mesure de complexité.
11 juil. 2006 à 07:44
D'accord, je comprends maintenant... Mon problème c'est que je suis parti de la définition suivante :
F : N -> N tel que
F(0) = 1
F(1) = 1
F(n) = F(n - 1) + F(n - 2)
Bon je corrige tout ça pour la définition suivante :
F : N -> N tel que
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2)
Merci pour ces indications et la note. Pour le troisième algo, tu as effectivement raison. Cela revient aux deux formules que tu cites. Pour la clarté, je suis aussi de ton avis. La raison vient du fait que ce programme est une traduction en VB d'une version en Caml où les opérateurs peuvent être réutilisés pour autre chose que leur utilisation de départ. Voici ce que ça donne :
=
(* Multiplication matricielle *)
let ( * ) a b = Array.init 2 (fun i -> Array.init 2 (fun j -> a.(i).(0) * b.(0).(j) + a.(i).(1) * b.(1).(j)))
(* Exponentiation rapide matricielle *)
let rec ( ** ) a = function
| 0 -> a
| 1 -> a
| n when n mod 2 = 0 -> (a * a) ** (n / 2)
| n -> a * (a * a) ** (n / 2)
let wild_fibonacci n ([| [|1 ; 1|] ; [|1 ; 0|] |] ** n).(0).(0)
Evidemment, sous ces conditions, * n'est plus la multiplication des entiers mais celle des matrices, et ** n'est plus la puissance d'un entier mais celle d'une matrice. Les formules paraissent alors plus claires, surtout dans la fonction d'exponentiation rapide ( ** ) qui a "presque" la même tête que dans le cas des entiers. Dommage... je ne crois pas que l'on puisse en faire autant en VB, et les appels de fonctions ne sont pas aussi parlants.
Pour le code le plus optimisé concernant une plage de valeurs, je crois qu'on peut répondre de façon assez simple :
1. Si les valeurs de n sont petites, les trois algos "se valent en pratique".
2. Si les valeurs sont très grandes, seul le troisième algo est vraiment efficace (ou alors la formule de Binet qu'il ne faut pas non plus oublier. On peut la réaliser très vite en supprimant le second terme trop petit et utiliser l'exponentiation rapide pour faire un calcul très rapide et sans les notions mathématiques plus "raffinées" que sont les matrices).
3. Si les données ont des propriétés singulières, mieux vaut sans doute reprogrammer quelque chose pour elles seules.
Par exemple, quand on programme la multiplication des polynômes ou des entiers, on sait qu'on aura une mauvaise complexité... quand les valeurs sont immenses, mieux vaut aller voir du côté de Fourier. Mais si c'est pour faire 10 * 5, eh eh, c'est un peu exagéré ;-)
Cordialement,
Cacophrène
11 juil. 2006 à 00:10
Pour ma part, c'est un 10/10. Y'a tellement matière à réflexion...
et, j'avoue que je reprendrai bien un p'tit bout de code, pour me faire une fonction Fibonacci sous Excel... :);
Sinon, on voit assez rarement les appels récursifs en programmation, donc cela donne un bon exemple... d'autant que cela donne un temps d'exécution bien meilleur...
Pour ton 3ième algo, je ne connais pas bien la syntaxe ("avancé") sous VB6, donc je n'ai pas encore pu le tester. Mais d'après ce que j'ai lu et si je comprend bien, ton calcul matriciel revient au même que d'utiliser les relations :
F(2n) = F(n)^2 + 2*F(n)*F(n-1)
F(2n+1) = F(n)^2 + F(n+1)^2
qui me semble aussi plus clair. En principe, la complexité est identique au calcul sous forme matriciel.
IL reste à trouver une programmation efficace... JE lance ce petit challenge courtois...
=
Un petit point de vue tout même. Sans rentrer dans tout le débat sur la complexité, à mon sens cette mesure, quoique très utile, n'est pas suffisante. Pour moi, je recherche l'algorithme le plus rapide (hors matériel) en exécution pour une plage donnée de valeur. Ceci mène en général souvent à choisir la complexité la plus faible, mais pas toujours... et force également à chercher la meilleur optimisation. Les différences pouvant être importantes.
=
Pour ce qui concerne tes remarques sur la complexité de l'algo que je propose, tu as entièrement raison : mon algo, n'est pas identique à ton 1er. D'ailleurs, je suis d'accord avec le reste aussi...
Pour le décalage, tu écris : "Attention je commence à zéro et pas à un (serait-ce la raison ?)"
ET bien justement, tu ne commence pas à zéro.... mais à un, c'est la raison ! Normalement, on doit avoir F(0)=0 ; F(1)=1 ; F(2)=1 ; F(3)=2 ...
Pour le 2ième algo, la correction est très simple, il suffit d'écrire dans FastFibonacci :
FastFibonacci = Auxiliary(0, 1, n)
au lieu de :
FastFibonacci = Auxiliary(1, 1, n)
Pour 1er algo, dans Fibonacci :
Select Case n
Case 0
Fibonacci = 0
Case 1
Fibonacci = 1
Case n 'Dans les autres cas, on utilise la relation classique définissant la suite de Fibonacci
Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
End Select
Hélas, pour le dernier, je te laisse chercher...
Amicalement,
Us.
10 juil. 2006 à 20:31
Merci pour ta note, jean_marc_n2. C'est toujours sympa quand une source plaît ou sert à quelqu'un.
Merci encore,
Cacophrène
10 juil. 2006 à 19:55
très sympathique source, une bonne initiation à la notion de complexité.
Je mets un 9/10, pour la qualité didactique de la chose :-)
10 juil. 2006 à 16:26
si résultat(n) déjà calculé alors retourner le résultat
faut voir, ça peut peut-être marcher finalement, mais c'est toujours bordélique de mélanger des variables globales avec du récursif.
10 juil. 2006 à 13:52
Il n'y a jamais de ridicule dans une intervention. Je crois que c'est ceux qui ne disent rien qui sont ridicules, quiand ils ont quelque chose à dire qu'ils ne disent pas !
Pour stocker un résultat dans une variable en récursif, le problème c'est que la sauvegarde se fera chaque fois... sauf peut-être en ajoutant un tableau et compteur passé en argument facultatif (Optional). Qu'en dis-tu ?
Cordialement,
Cacophrène
10 juil. 2006 à 13:47
Maintenant, pour éviter le ridicule de mon intervention, il faudrait que je trouve un moyen de stocker cette variable quelque part, mais à priori, cela risque fort de ressembler à du super-bricolage à la mord-moi-l'noeud (ou alors carrément génial ?), à supposer même que cela soit possible sans changer la complexité de l'algo ! bigre !
10 juil. 2006 à 13:29
Remplacer
...
Case n
If n Mod 2 = 0 Then
FastPower = (x * x) ^ (n \ 2)
Else
FastPower = x * (x * x) ^ (n \ 2)
End If
...
par
...
Case n
If n Mod 2 = 0 Then
FastPower = FastPower(x * x, n \ 2)
Else
FastPower = x * FastPower(x * x, n \ 2)
End If
...
Merci
10 juil. 2006 à 13:27
Pour te répondre, je te propose de reprendre en guise d'exemple deux des algorithmes qui figurent dans ma source ici même. Voyons d'abord le premier algo :
=
Public Function Fibonacci(n As Long) As Long
Select Case n
Case 0, 1
Fibonacci = 1
Case n
Fibonacci = Fibonacci(n - 1) + Fibonacci(n - 2)
End Select
End Function
=
Nous utilisons ici la définition classique de la suite de Fibonacci. Pour déterminer la complexité de cet algo, il suffit de considérer que la relation par récurrence F(n) = F(n - 1) + F(n - 2) a pour équivalent la formule de Binet :
1/Racine(5) * [((1 + Racine(5)) / 2) ^ n + ((1 - Racine(5)) / 2) ^ n]
Si nous passons à la limite pour n tendant vers l'infini, il ne reste que le premier terme (avec phi le nombre d'or), et donc 1 / Racine(5) * phi ^ n donne, en notation de Landau, un O(phi ^ n). Quitte à être moins précis, on peut montrer par récurrence que l'on est en O(2 ^ n). C'est moins précis mais ça revient "presque" au même : nous sommes dans l'idée d'une complexité exponentielle. Nous mesurons la difficulté d'une tâche à accomplir. "Intrinsèque" oui et non. Il n'y a pas de complexité "absolue". Changer d'algorithme fait changer de complexité.
Considérons maintenant le deuxième algo :
=
Public Function FastFibonacci(n As Long) As Long
FastFibonacci = Auxiliary(1, 1, n)
End Function
Private Function Auxiliary(a As Long, b As Long, n As Long) As Long
Select Case n
Case 0
Auxiliary = a
Case n
Auxiliary = Auxiliary(b, a + b, n - 1)
End Select
End Function
=
Ici, tu vois que l'appel récursif à Auxiliary(b, a + b, n - 1) indique que nous avons en tout n - 1 additions à effectuer (on peut formaliser davantage au besoin). Nous sommes donc dans le cadre d'une complexité linéaire, soit en notation de Landau : O(n).
Or, comme tu me le diras, entre ces deux algos, il n'y a en fait qu'une meilleure utilisation des opérations et surtout des variables, ce qui évite de recalculer sans cesse les mêmes valeurs. Cette meilleure utilisation conduit à une grande amélioration des performances.
C'est un peu la même chose pour les algorithmes d'exponentiation classique et d'exponentiation rapide. Si j'écris :
Function Power(x As Integer, n As Integer) As Integer
Select Case n
Case 0
Power = 1
Case n
Power = x * Power(x, n - 1)
End Select
End Function
Dans ce cas je suis dans le cadre d'une complexité linéaire. Or si j'utilise une "astuce" pour réduire le nombre d'opérations, je peux tomber dans une complexité meilleure, logarithmique, en rédigeant :
Function FastPower(x As Integer, n As Integer) As Integer
Select Case n
Case 0
FastPower = 1
Case 1
FastPower = x
Case n
If n Mod 2 = 0 Then
FastPower = (x * x) ^ (n \ 2)
Else
FastPower = x * (x * x) ^ (n \ 2)
End If
End Select
End Function
Tu vois bien qu'il s'agit d'une autre présentation, pas foncièrement très différente de la précédente, hormis que nous avons, presque sans y songer, transformer un algo rapide en un algo beaucoup plus rapide.
Conclusion : La complexité est une mesure de l'efficacité des algorithmes, indépendamment du matériel (langage, processeur, compilateur, etc...). Et c'est aux API que l'on peut demander une approche plus expérimentale de la question, par le biais de moyennes. Un bon article Wikipédia sur le sujet : http://fr.wikipedia.org/wiki/Complexité_algorithmique
Voilà. J'espère avoir répondu aussi clairement que possible à la question.
Cordialement,
Cacophrène
10 juil. 2006 à 11:46
Exemple :
- Somme de 1 à n : algorithme de complexité en O(n), car il y a une boucle jusqu'à n ;
- n*(n+1)/2 : complexité en O(1) : une seule instruction, alors que le résultat est le même que le précédent !
10 juil. 2006 à 11:03
La mesure de la complexité d'un algorithme peut se faire selon trois méthodes :
1. Le meilleur des cas possibles
2. Le cas moyen (coût moyen)
3. Le pire des cas possibles (coût maximal)
Par exemple, l'algorithme du tri rapide (quicksort) est quadratique (en O(n²)) dans le pire des cas, et quasi-linéaire (en O(n * log n)) dans le cas moyen.
Ici, je propose trois algorithmes utilisant des formules connues :
a) Un algorithme naïf de complexité exponentielle O(phi ^ n).
b) Un algorithme évolué de complexité linéaire
c) Un algorithme avec calcul matriciel de complexité logarithmique.
La complexité est ici mesurée en nombre d'additions à effectuer. Il n'est pas question d'optimisation de code. Les trois algorithmes sont, dans leur genre propre, déjà optimisés. Toute amélioration comme par exemple sauvegarder la somme (comme l'a fait us_30) revient à changer d'algorithme et donc de complexité. C'est la raison pour laquelle nous obtenons des temps si différents.
Et de répéter, à la suite de Patrice99 qui l'a dit très justement : rien à voir avec l'optimisation. Trois algos distincts, trois complexités distinctes, et donc trois performances distinctes.
Cordialement,
Cacophrène
10 juil. 2006 à 08:27
10 juil. 2006 à 08:14
La version que tu me proposes ne correspond pas à mon premier algorithme. Il y a deux raisons à cela : la première, c'est bien évidemment la différence de temps vertigineuse entre les deux algorithmes (oui, ne rêvons pas, 0,002 secondes pour un algo exponentiel, c'est douteux). La seconde, c'est que tu sauvegardes le résultat m1 + m2 et que tu opères une substitution exactement comme mon second algorithme avec fonction auxiliaire. Le premier algorithme, quant à lui, est bel et bien naïf parce que son coût en temps est prohibitif (comme tu as pu le voir... 9 secondes !). Sa complexité exponentielle (en O(phi ^ n) avec phi le nombre d'or) indique que pour calculer Fibonacci(32), on doit s'attendre à plusieurs millions d'opérations (le calcul exact importe peu, surtout avec la notation de Landau). Pourquoi ? Tout simplement parce qu'on demande de calculer deux fois toutes les valeurs. C'est ce qui se passe lorsque l'on écrit Fibonacci (n - 1) + Fibonacci (n - 2). Le programme commence par calculer Fibonacci (n - 1), qui demande Fibonacci(n - 2) et Fibonacci (n - 3)... Mais Fibonacci(n - 2) demande Fibonacci(n - 3) et Fibonacci (n - 4), etc... Nous recalculons sans cesse les MÊMES valeurs, et dans une telle mesure que cela devient ridicule.Ton algorithme, lui, ne fait pas tous ces calculs. Il en fait beaucoup moins. Pour le décalage, je suis étonné et je ne vois pas où est l'erreur... Attention je commence à zéro et pas à un (serait-ce la raison ?). Si tu as de plus amples indications à me fournir pour corriger ce problème, je suis preneur.
Cordialement,
Cacophrène
9 juil. 2006 à 19:04
Autre petit détail :
F(32)= 2178309
F(33)= 3524578
Les algos donnent pour n=32, la valeur pour n=33... Un p'tit décalage de 1 -:);
Amicalement,
Us.
9 juil. 2006 à 18:43
OK, merci.
JE vais tout de même de tester tes 2 premiers algo qui fonctionnent sous VB5... JE suis trés étonné de la trés trés faible performance de ton 1er algo, dit "naïf"... c'est à dire qui utilise la réccurrence de la définition... En effet, j'obtiens un peu 9 secondes (sur mon PC)... Je veux bien admettre que ce n'est pas l'algo le plus performant, mais delà à obtenir un temps si long pour juste quelques sommes !...
J'ai refait ce premier algo à ma sauce, et c'est sans comparaison. J'obtiens 0,002 seconde ! (et en Double)
JE pense qu'il y a un truc qui doit faire chuter les perfs...
Voici mon algo :
=
Function Fibonacci(ByVal n As Integer) As Double
'Suite des nombres de finabocci
Dim m1 As Double, m2 As Double, t As Integer, temps As Double
Finabocci = 1
m1 1: m2 1
temps = Timer
For t = 3 To n
Fibonacci = m1 + m2
m1 = m2
m2 = Fibonacci
Next t
MsgBox Timer - temps
End Function
=
Voilà... c'est une première remarque...
Pour ton second algo, j'obtiens 0,0006 seconde, donc toujours mieux...
A+
Amicalement,
Us.
9 juil. 2006 à 17:21
Il faut utiliser VB6.
A bientôt,
Cacophrène
9 juil. 2006 à 17:18
Oui, c'est ce que je voulais demander. Donc quelle version utiliser ?
Amicalement,
Us.
9 juil. 2006 à 17:13
Juste une précision : n'essayez pas d'utiliser ce module avec VB5 car vous rencontrerez des problèmes de validité pour certaines lignes.
Cordialement,
Cacophrène