Komplexität von Algorithmen

Hi Leute,

Wie kann man genau die Komplexität von ALgorithmen bestimmen?
Kennt ihr eine gute Site, wo die Verfahren der Komplexitätsbestimmung gut und einleuchtend erläutert sind.

Bsp.:

for(i=N; i>=1; i--) 
{
  for(j=1; j<=i; j++)
  {
  if(a[j-1] > a[j])
     swap(a,j-1,j);
  }
}

beträgt hier O(n²)
aber wie kann man es beweisen.

Danke schonmal vorab.

Cu

Sgt. Nukem

2 Schleifen, die jeweils über alle Eingabewerte laufen (n) macht n * n

Man könnte in die Schleifen für jede "atomare Operation" (hier nur konditionales Swappen) die ausgeführt wird, einen Zähler erhöhen, und nachher in Beziehung zu n setzen!

komplexität von algorithmen hat i.A. zwei Komponenten Speicherbedarf und Zeitbedarf.
Das mit dem O (Landausche O Notation), ist im Endeffekt nur sehr gerne für den Zeitbedarf von Algorithmen verwendet und daher gerne gleichgesetzt.
Schleifenzählen reicht meist aus um die LAufzeit (natürlich nicht die absolute) eines Algoritmus abzuschätzen....du kannnst da aber auch noch ein weng tiefer in die Theorie einsteigen.
Such einfach mal nach allen skripten von theoretischer Informatik und komplexitätstheorie.
Aber falls Du Dir in der Richtung was antun willst: Verwechsle nicht die Komplexität eines Algorithmuses mit der Komplexität eines Problems.

schau Dir halt mal sowas an:
http://www-hm.ma.tum.de/archiv/in2/ss02/vorlesungen/v020606/O.pdf