Home
News
Entwicklung
Programm
  Verifizierung
  Rechenaufwand
  API-doc
  Source
  Betriebsanleitung
  Applet
Download
 
Aufwand
 
  Da wir festellten dass die zeit um eine Matrix zu lösen mit grossen n relativ viel Zeit benötigt, wollten wir natürlich wissen wie die Zeit in abhängigkeit von n wächst.
    Nach unseren Analysen berechnet sich die anzahl schleifendurchläufe in der Gausselimination mit



    Der Aufwand des Rückwärts einsetzen beläuft sich mit:



    Diese addiert und ausgerechnet ergibt:


    was sich nach BigO als

      O(n3)

    auswirkt.
    Da für ein durchnittlich belegtes Gitter n ungefähr der Anzahl Punkten im Gitter entspricht gilt:

      n=x*y

    daraus ergibt sich bei einem quadratischen Gitter der Breite h

      n=h2 --> O(h6)

    was relativ viel ist.

    Messung

    Wir haben nun die Rechenzeit in abhänigkeit der Gitterhöhe gemessen und Tabellarisch und Graphisch dargestellt. Dabei haben wir die erhaltenen Werte mit h6 verglichen

    h time in ms h6 time/h6
    1 1 1 1
    10 41 1000000 0,000041
    20 2814 64000000 4,39688E-05
    25 8452 244140625 3,46194E-05
    30 29543 729000000 4,05254E-05
    35 99493 1838265625 5,41233E-05
    38 123998 3010936384 4,11825E-05

    da ganz klar zu erkennen ist das das Verhältnis time/h6 bei anständigen h in etwa gleich bleibt, bestätigt unsere Annahme der Aufwand gehe mit O(h6).

    Das Diagramm der obigen Tabelle:





  
© by w3p.ch 2001   Project copyright Fabian Heusser; Daniel Schröter; to the top