„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
aNincs szerkesztési összefoglaló |
|||
| 46. sor: | 46. sor: | ||
*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)'' | *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: | :::::::::::::::::[[File:Algel zh 2013tavasz A B matrix.PNG|400px]] | ||
}} | }} | ||
| 73. sor: | 73. sor: | ||
**Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | **Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Post tabla.png|400px]] [[File:Algel zh 2013tavasz Graf.png|300px]] | ||
}} | }} | ||
| 90. sor: | 90. sor: | ||
**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | **A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | ||
*Így a feladat ezzel meg is oldva. | *Így a feladat ezzel meg is oldva. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Csucs suly.png|300px|G gráf]][[File:Algel zh 2013tavasz El suly.png|400px|F gráf]] | ||