Laufzeitabschätzung < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:59 So 18.07.2010 | | Autor: | matheja |
| Aufgabe | Hallo Leute.
ich lerne für eine Klausur und habe ein Problem mit der Laufzeitabschätzung von Java- Programmen in O-notation (worst- case).
Es wär toll wenn mir das jemand an einem kleinen Programm erklären könnte.
Als Beispiel wähle ich folgendes Programm:
/**
* Finde das groesste Element in einem
* zweidimensionalen quadratischen int-Array
*/
int gibGroesstesElement(int[][] a)
{
int element = Integer.MIN;
int n = a.length;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (element < a[i][j])
element = a[i][j];
return element;
}
|
Wie geht man vor, wenn man ein kleinen Code in 0-notation abschätzen möchte?
Meine Überlegungen:
Wertzuweisung, Schleifeninitialisierung,
Bedingungsüberprüfung, Schleifeniteration und if-Bedingungsprüfung benötigen jeweils ein schritt:
/**
* Finde das groesste Element in einem
* zweidimensionalen quadratischen int-Array
*/
int gibGroesstesElement(int[][] a) // 1 schritt
{
int element = Integer.MIN; // 1 schritt
int n = a.length; // 1 schritt
for (int i=0; i<n; i++) // 1+1+1=3 * n (anzahl der durchläufe äußere schleife)
for (int j=0; j<n; j++) // 1+1+1=3 * n(anzahl der durchläufe
innere schleife)
if (element < a[i][j]) // 1+1=2
element = a[i][j]; // 1
return element;
}
=> 3n*3n +2+2+1= [mm] 6n^2+5=> =O(n^2)
[/mm]
ich bin mir sehr sicher, mirr würde es echt sehr helfeb, wenn mir jemand das sehr genau erklären könnte.
mfg
matheja
|
|
| |
|
Hallo!
Das ist korrekt, die Ordnung ist quadratisch.
Um die Ordnung zu berechnet, schaut man sich aber normalerweise nur die Schleifendurchläufe an. Das Initialisieren von Variablen hat keinen Einfluß auf die Ordnung, die Schleifen sind das, was ständig durchlaufen wird.
Nebenbei ist dein Algorithmus linearer Ordnung bezüglich der Anzahl der Felder, weil er über jedes Feldelement einmal drüber geht. Der quadratische Zusammenhang kommt einfach daher, daß hier [mm] $n\times n=n^2$ [/mm] Elemente gegeben sind.
|
|
|
|
