Discussion :

[membreComplexe12]

salut tous,

j'ai quelques infos à vous demandez :

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

2°) comment calcul t on la complexité d'un algorithme, pourriez vous me donner deux exemples simples s'il vous plait ?

- cas du déterminant
- cas de la resolution d'une matrice triangulaire.

je vous remercie d'avance pour l'aide pour que vous pourrez m'apportez

[FR119492]

Salut!
A quoi cela sert-il de calculer le déterminant d'une grosse matrice?
Jean-Marc Blanc

[Franck Dernoncourt]

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

2°) comment calcul t on la complexité d'un algorithme, pourriez vous me donner deux exemples simples s'il vous plait ?

- cas du déterminant
- cas de la resolution d'une matrice triangulaire.

je vous remercie d'avance pour l'aide pour que vous pourrez m'apportez

Je n'ai pas de bons liens sous la main, mais peut-être que http://www.algo-class.org/ t'intéressera (ils vont probablement étudier la complexité à un moment). Sinon, en matière d'études d'algorithmes, le livre de référence est http://algo.developpez.com/livres/#L9782100545261

[membreComplexe12]

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

Je n'ai pas de bons liens sous la main, mais peut-être que http://www.algo-class.org/ t'intéressera (ils vont probablement étudier la complexité à un moment). Sinon, en matière d'études d'algorithmes, le livre de référence est http://algo.developpez.com/livres/#L9782100545261

merci Franck mais je n'ai pas vraiment trouvé de démonstration/explications simple dans ces liens.... (pour cette question à priori simple également...)

en fait je cherche une explication pour une personne débutante là dedans, j'aimerai plus une explication de la demarche à suivre pour calculer la complexité des algo..

[Franck Dernoncourt]

merci Franck mais je n'ai pas vraiment trouvé de démonstration/explications simple dans ces liens.... (pour cette question à priori simple également...)

Oui je sais, mais je répondais à ta question :

1°) si je comprends bien le calcul de déterminant fait intervenir autant de boucle que la taille de la matrice ?

du coup si je veux calculer un determinant de 1e6*1e6 comment dois je faire ? les temps de calcul vont être enorment ?

(meme chose pour le calcul d'une matrice inverse puisqu'il y a un determiant ?)

Pour les démonstration/explications du calcul de la complexité des algorithmes permettant de calculer l'inverse ou le déterminant, il faut simplement les chercher sur Google en espérant qu'il y existe des documents clairs.

en fait je cherche une explication pour une personne débutante là dedans, j'aimerai plus une explication de la demarche à suivre pour calculer la complexité des algo..

Désolé, hormis les liens que je t'ai mentionnés précédemment (dont j'ai conscience qu'ils ne sont pas pratiques pour comprendre rapidement l'étude de la complexité), je n'ai pas de ressources simples en tête

[membreComplexe12]

Oui je sais, mais je répondais à ta question :
Pour les démonstration/explications du calcul de la complexité des algorithmes permettant de calculer l'inverse ou le déterminant, il faut simplement les chercher sur Google en espérant qu'il y existe des documents clairs.

Désolé, hormis les liens que je t'ai mentionnés précédemment (dont j'ai conscience qu'ils ne sont pas pratiques pour comprendre rapidement l'étude de la complexité), je n'ai pas de ressources simples en tête

d'accord, merci quand même de ton aide Franck

A+

[Franck Dernoncourt]

Si quelqu'un passant ici connaît une bonne ressource (site Internet, pdf, etc) expliquant clairement la méthode pour déterminer la complexité d'un algorithme, svp faites-le nous savoir !
Personnellement j'ai appris les bases par transmission orale (c'est assez simple au final une fois que l'on trouve une source claire) et perfectionné essentiellement sur http://algo.developpez.com/livres/#L9782100545261 (version anglaise et deuxième édition pour être précis, c'est une mauvaise idée de l'acheter en français)

[Franck Dernoncourt]

Ah oui? Avec quelle approche obtient-on cette borne?

Voici les complexités des algorithmes habituels : http://en.wikipedia.org/wiki/Computa...Matrix_algebra

(je sais que l'on s'y perd avec tous ses liens )

[Franck Dernoncourt]

Je t'avouerai cependant que je ne me suis jamais penché en détail sur les meilleurs algorithmes (ce n'est pourtant pas la curiosité qui me manque, mais comme toujours le temps), donc aucune idée de leur fonctionnement !

[Aleph69]

Pour les cas pratiques, ce n'est pas très intéressant d'utiliser ces algorithmes : ils sont numériquement instables.