Exekveringstid Gauss-eliminering och LU-dekomposition

LU-faktorisering är $\mathcal O{(n^3)}$. Vissa källor talar för att komplexiteten ligger mellan $n^2$ och $n^3$, men du kan nog räkna med $\mathcal O(n^3)$. :)

Hej,

Svaret ska bli 8s

Om tid för varje iteration med Gauss är c= 2/100^3 

Då blir tiden för en iterations med LU dekomp. T= c*200^3 = 16s

Så, det stämmer inte att båda har samma 

Om en algoritm är O(n³) och en annan är O(n²) kan man inte dra några slutsatser av att det tar en viss tid med den ena. De har förmodligen olika proportionalitetskonstanter, dvs. den första är ungefär an³ och den andra är bn² och vi vet ingenting om förhållandet mellan a och b.

Om de menar att LU-dekomposition och Gauss-eliminering är nästan samma sak (men att man kan återvända LU-dekompositionen om man har flera olika högerled) då är båda O(n³) med samma proportionalitetskonstant och då kan man säga något. Men då verkar det som om de betraktar algoritmen som O(n²) eftersom 8 = 2^2.2.

Hur lyder hela problemtexten?

Hej,
Det är hela problemtexten. 

För de andra uppgifter används det att för Gauss eliminering är T=c*n^3. Det betyder att dators beräkningshastighet är c= 2/100^3 

Om det är T=c* n^2 för LU faktorisering  blir det T= 2/100^3  * 200^2 = 0.08s 

Båda borde då vara T=c*n^2 för att det ska bli 8s.

Kan du ta en bild på uppgiften? 

Konstanten c för en viss algoritm beror förvisso av datorns hastighet, men den är inte ett mått på den. c beror på algoritmen och hur den är implementerad.