Komplexität gesucht

[techdevil]

Hi,

N ist ein Array mit n Elementen.

for(int i=0;i<N.length;i++){
	      for(int j=i+1;j<N.length;j++){
                Konstanter Aufwand
    }
}

Gesucht ist jetzt die Laufzeit-Komplexität von diesem Algorithmus bezogen auf die Problemgröße n.
Mich irritiert, dass das Problem in der inneren Klammer ja jeweils um 1 reduziert wird..

 

[Der Müde Joe]

erstes for:
n mal
zweites for
(n-1) + (n-2) ... (1) --> n mal
-->
O(n^2)

genau:
( (n-1) + (n-2) ... (1) ) --> n * (n+1)/2 )

(wenn ich mich da nicht irre ???:L)

 

[function]

ist es nicht:
n* (n-1)n/2
wegen (n-1) + (n-2)... + 1) => (n-1)(n-1+1)/2...

 

[techdevil]

(n-1)+(n-2)+...+2+1 = n*(n-1)/2

Das ganze mal n wäre n²*(n-1)/2

Also O(n²).
Klingt plausibel...

 

[Der Müde Joe]

>ist es nicht:

hmmm...papier hervornehm..

Summ(1 - (n- 1) = 1 +___ 2__ + .... + (n-2) + (n-1)
Summ(1 - (n- 1) = (n-1) +(n-2) + ... +___ 2 + 1

2 Sum = (1 + (n-1)) + (2+ (n-2) .....
2 Sum = n + n + n...
2 Sum = n ( n- 1)
--> n(n-1)/2

(stimm das?)

EDIT:
>Das ganze mal n wäre n²*(n-1)/2
--> Das wäre dann aber n^3 ;-)

Die aussere Schleife n mal, die innere n mal (halt immer ein wenig weniger)
n * n --> n^2 (eben genau n*(n-1)/2 )

 

[techdevil]

Da steig ich jetzt grad nicht dran lang...
Kannst du das Ergebnis bitte nochmal prägnant formulieren, Joe

 

[javimka]

Es ist O(n^2)

 

[function]

jo es ist O(n^2)
hatte einen gedankenfehler drin genau wie joe...
man muss am ende nicht mehr n multiplizieren. Weil die Reihe den gesamt Durchlauf audrück und nicht nur den inneren...

 

[faetzminator]

Es ist O(n^2)

Du hast wohl [c]int j=i+1[/c] nicht beachtet 😉 ?

 

[Marco13]

Das ändert daran nichts. Es ist übrigens auch O(a(n)), wobei a(n) die Ackermannfunktion ist 😀

 

[javimka]

Du hast wohl [c]int j=i+1[/c] nicht beachtet 😉 ?

Mit der Summenformel kommt man auf ein Polynom, dessen führendes Monom n^2 ist. Deshalb ist die Laufzeit O(n^2).

Gaußsche Summenformel ? Wikipedia