„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 35. sor: | 35. sor: | ||
*Majd kitöltjük az 1. oszlopot <math> \rightarrow B[1,i]:=B[1,i-1]+A[1,i], i=2 \dots n </math>. ''(ez <math>\Rightarrow 2(n-1)=O(n)</math> lépés)'' | *Majd kitöltjük az 1. oszlopot <math> \rightarrow B[1,i]:=B[1,i-1]+A[1,i], i=2 \dots n </math>. ''(ez <math>\Rightarrow 2(n-1)=O(n)</math> lépés)'' | ||
*Minden további cellában pedig <math> B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] </math>. ''(ez <math>\Rightarrow 4(n-1)(n-1)=O(n^2)</math> lépés)'' | *Minden további cellában pedig <math> B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1] </math>. ''(ez <math>\Rightarrow 4(n-1)(n-1)=O(n^2)</math> lépés)'' | ||
*A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j | *A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)'' | ||
*<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | *<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | ||
:::::::::::::::::[[File:A_B_matrix.PNG|400px]] | :::::::::::::::::[[File:A_B_matrix.PNG|400px]] | ||