Drei Schleifen Komplexität

Question

Kann mir jemand die Komplexität des untenstehenden Codes sagen und die Berechnungen erklären?

int count=0; 
for(int i=0; i<n;i++) 
    for(int j=i; j<n;j++) 
     for(int k=j;k>i;k--) 
      count++; 

Dank

Answer 1

Dies ist nur eine "einfache" Mathematik:

für die erste Schleife, seine ganz einfach, es n Iterationen tun.

zweite Schleife ist nicht so viel komplizierter:

• i=0: Sie n Iterationen haben.
• i=1: n-1 Iterationen
• i=2: n-2 Iterationen
• ...
• i=n-1: 1 Iteration

Summe ist n(n+1)/2.

Für dritte Schleife, sind wir nur daran interessiert, wenn j>i:

• i=n-1: Sie 0 Iteration haben.
• i=n-2: 1 Iteration, und das ist, wenn j=n-1
• i=n-3: 2 Iteration, wenn j=n-1 und 1 Iteration, wenn j=n-2
• i=n-4: 3 Iteration, wenn j=n-1, 2 Iteration, wenn j=n-2, 1 Iteration, wenn j=n-3
• ...
• i=0: n-1 Iteration, wenn j=n-1, n-2 Iteration, wenn j=2, ..., 1 Iteration, wenn j=1

Laufzeit dieser ist:

O((n-1)n/2 + (n-2)(n-1)/2+...+(n-n+2)(n-n+1)/2+(n-n+1)(n-n)/2)=O((n-1)*(n^2)/2)=O(n^3)