O notation

[heppi75]

hallo,

habe zwar einige beiträge gefunden doch ich tu mich sehr schwer die O notation zu verstehen.

ich habe folgendes beispiel:

static void schleife(int n)
    {
	for(i=1; i <= 3*n; i++)
	for(j=1; j <= i; j++)
	zaehler++;
    }

nun die entscheidenden fragen. welche laufzeitformel und welche komplexitätsklasse?

wenn sich jemand die zeit nehmen könnte wäre ich dankbar - auch vielleicht nochmal für eine erklärung vom ergebnis ... - danke!

 

[HimBromBeere]

Was macht denn

O(3n) * [O(n) + O(n - 1) + ... + O(1)]

?

[EDIT]So, jetzt sieht´s besser aus...[/EDIT]

 

[SlaterB]

was du selber doch mindestens leicht machen könntest, wäre eine Wertetabelle,
zaehler ist sogar schon drin, nur dessen Wert für n = 10, 100, 1000 ausgeben

falls das noch nicht eindeutig ist, vielleicht auch paar typische Klassen aufzählen
mit gar vermuteten/ berechneten typischen Werten für n = 10, 100, 1000 😉

 

[heppi75]

also O(n)?

und was ist die laufzeitformel?

3n²
3n²/2
3n²/4
(9n²+n)/2
3(n(n+1))/2
3n(3n+1)/2

 

[hüteüberhüte]

3*n kannst du ignorieren, geh einfach von n aus. Dann ergibt sich n+(n-1)+(n-2)+...+1=n(n+1)/2=O(n^2), die Komplexität

Was bedeutet für dich denn Laufzeitformel?

 

[hüteüberhüte]

Also die Laufzeit wäre O(n^2) (siehe: Big O notation - Wikipedia, the free encyclopedia ), also quadratisch, damit wäre die Komplexitätsklasse P