Discussion :

[ahcnas]

salut
j'ai un algorithme de complexité 2*N*N*T (nombre de multiplications =N(N+1)(T-1)+N nombre d'additions=N(N+1)(T-1)+N).
s'il vous plait je veux calculer la complexité de l'algorithme dont je l'ai divisé en sous problèmes sachant que chaque sous problème à la complexité 2n*n*T (avec n<<< N) (nombre de multiplications =n(n+1)(T-1)+n nombre d'additions=n(n+1)(T-1)+n)

[souviron34]

salut
j'ai un algorithme de complexité 2*N*N*T (nombre de multiplications =N(N+1)(T-1)+N nombre d'additions=N(N+1)(T-1)+N).
s'il vous plait je veux calculer la complexité de l'algorithme dont je l'ai divisé en sous problèmes sachant que chaque sous problème à la complexité 2n*n*T (avec n<<< N) (nombre de multiplications =n(n+1)(T-1)+n nombre d'additions=n(n+1)(T-1)+n)

Non, c'est faux..

Si tu as :

nombre de multiplications =N(N+1)(T-1)+N

alors complexité est T*N^2

Pareil pour les additions...

Donc complexité de l'algo est la même : O(T*N^2)