,  
J ai une matrix nXm (col * rows) et un nombre P
je test differentes decoupes  column et rows, qui se resume a traverser la matrix deux fois donc col*rows *2
Ensuite en utilisant divide and conqueer, je fait subir le meme processus aux deux sous matrices chacune se partageant P/2 (si paire)
jusqu a ce que P soit egal a 1.
 
quel serait la complexiter en big O ? big Theta (fct inferieur)? big Omega (fct superieur) ?
 
je sais que divide and conquer est n log n. mais dans mon cas ce devrais changer un peu non ?

j'ai rien compris
 
mais on écrit algorithme

 
 
c'est clair que ca a l'air complexe  

Et la ?
chaque partition demande col*rows *2 operations avant de savoir ou coupe.

 
haha en prime le correcteur orhto en anglais.

on appelle pas ca complexite dun algo en francais ?
O(n) ect

 
en français ça donne: complexité d'un algorithme  

Tu aurais pu continuer le thread précédent (http://forum.hardware.fr/hardwaref [...] 5337-1.htm) au lieu d'en créer un nouveau, ça t'aurait évité de devoir réexpliquer...
 
Je peux me tromper mais voilà ma réflection:
A chaque étape, on doit parcourir au moins une fois tous les éléments de la matrice pour trouver la meilleur partition. Par exemple, on commence avec P=8. On doit parcourir tous les éléments pour trouver la meilleure partition. On se retrouve avec deux sous-problèmes où P=4. Pour ces 2 sous-problèmes pris ensembles, on doit à nouveau parcourir tous les éléments de la matrices, etc jusqu'à ce que P=1.
La complexité est donc O(N*M*log(P)), vu qu'il faut de l'ordre de log(P) étape pour arriver à P=1.
Quelques mesures effectuées semblent confirmer ce résultat lorsque P << N*M (P bcp plus petit que N*M). Dans mes tests, ca colle assez bien tant que P < N, mais je n'ai essayé qu'avec des matrices carrées contenant des élements choisis aléatoirement avec un distribution uniforme.
Toutefois, il manque certainement une partie du raisonnement vu que lorsque P est plus grand, le temps de calcul augmente significativement et je ne sais pas trop comment l'expliquer.

jai fait aussi letude de mon cote et voila ce que jai trouve

le seul truc que je ne suis pas trop sur cest lapplication du master theorem, ou doit aller le 4.

Le 4 on s'en fout, Theta est défini à une constante près:
Theta(4*n) = Theta(n) = 4 * Theta(n) ...
 
Mais je ne suis pas sûr de te suivre dans ton raisonnement. Comment P disparait de l'équation ? Cela voudrait dire que la complexité asymptotique est indépendante de P ?
(j'utilise 'O' au lieu de 'Theta' car c'est plus lisible, mais il s'agit vraiment de Theta)
T(n,p) = 2 T(n/2,p/2) + O(n)
--> T(n/2,p/2) = 2 T(n/4,p/4) + O(n/2)
--> T(n,p) = 4 T(n/4,p/4) + 2 O(n)
--> T(n,p) = 8 T(n/8,p/8) + 3 O(n)
...
On sait que T(n,1) = O(n).
Comme p <= n, on arrivera à p=1 avant d'arriver à n=1
--> T(n,p) = p T(n/p, 1) + O(log p) * O(n)
--> T(n,p) = p O(n/p) + O(n log p)
--> T(n,p) = O(n) + O(n log p)
--> T(n,p) = O(n log p)
 
Mais j'ai fait l'hypothèse que la matrice est à chaque fois divisée en 2 parties égales (d'où le n/2 dans la récurrence), cette démonstration n'est donc pas générale. Elle nous donne donc tout au plus une borne inférieure de T(n,p).
 
Essayons un cas particulier, pour nous faire une idée:
supposons que la matrice est une matrice-ligne (un vecteur): 1 x n. Prenons le cas où, à chaque division, un seul élément est séparé du reste.
T(n,p) = T(n-1, p/2) + T(1,p/2) + O(n)
--> T(n-1,p/2) = T(n-2, p/4) + T(1, p/4) + O(n-1)
et  T(1,p) = O(p/2) (il faut bien dire à tous ces processeurs sauf 1 qu'ils ne doivent rien faire)
--> T(n,p) = T(n-2, p/4) + O(p/4) + O(n-1) + O(p/2) + O(n)
...
--> T(n,p) = T(n-log p, 1) + [O(p/2) + O(p/4) + O(p/8) + ... + O(1)] + [O(n) + O(n-1) + O(n-2) + ... + O(n-log p)]
log p est négligeable par rapport à n (puisque p <= n)
--> T(n,p) = O(n) + O(p) + O(n)*log p
O(p) <= O(n)
--> T(n,p) = O(n*log p)
 
Même résultat...
 
Cela me donne une idée pour trouver une borne supérieure dans le cas général:
T(n,p) = T(n1,p/2) + T(n-n1,p/2) + O(n)    ; 0 < n1 < n
En réalité, la valeur de n1 sera plus contrainte: elle sera toujours un multiple du nombre de lignes ou de colonnes de la matrice considérée.
T(n1,p/2) = T(n2,p/4) + T(n1-n2,p/4) + O(n1)         ; 0 < n2 < n1
T(n-n1,p/2) = T(n3,p/4) + T(n-n1-n3,p/4) + O(n-n1)   ; 0 < n3 < n-n1
-->
T(n,p) = T(n2,p/4) + T(n1-n2,p/4) + O(n1) + T(n3,p/4) + T(n-n1-n3,p/4) + O(n-n1) + O(n)
T(n,p) = T(n2,p/4) + T(n1-n2,p/4) + T(n3,p/4) + T(n-n1-n3,p/4) + 2*O(n)
Cela commence à faire bcp de paramètres, essayons de voir vers quoi nous allons
Après (log p) étapes, nous aurons  
T(n,p) = S + O(n*log p)
où S est une somme de p termes de la forme T(n_i, 1) (avec n_i qui varie)
T(n_i, 1) = O(n_i).
Essayons donc de majorer cette somme...
Cela n'est pas bien compliqué... Vu que l'on divise chaque fois la matrice en sous-matrices distinctes, la somme de tous les n_i sera toujours égale à n...
Par exemple, dans le développement ci-dessus: n2 + n1-n2 + n3 + n-n1-n3 = n
Donc T(n,p) = O(n) + O(n*log p) = O(n*log p)
 
Ouf
Nous y voilà. La borne supérieure est égale à la borne inférieur donc  T(n,p) = O(n*log p) dans le cas général.
C'est peut-être pas très rigoureux, mais si qq'un voit une faute dans le raisonnement, je serais intéressé de la connaître.