Ist die zeitliche Komplexität dieser Funktion O (N)?

Question

Was ist die zeitliche Komplexität dieser Funktion? Die Funktion gibt den kleinsten Wert im Array zurück. Ich denke, es ist O(N), aber ich kann es nicht beweisen. Jede Hilfe wäre willkommen!

int[] foo(int arr[], int N) 
{ 
    int k = 1; 
    while(k < N) 
    { 
     for(int i = 0; i+k<N; i+=2*k) 
     { 
     if(arr[k] > arr[i+k]) 
     { 
      swap(arr[i], arr[k+i]); //swap values in arr[i] and arr[k+1] 
     } 
     } 
     k = k*2; 
    } 

    return arr[0]; 
} 

Answer 1

Es ist O(N).

Es mag auf den ersten Blick wie O(NlogN) erscheinen, aber:

• erste innere for-Schleife: i = 0, 2, 4, 6, 8, ... dh N/2 Operationen
• zweite innere for-Schleife: i = 0, 4, 8, 12, 16, ... dh N/4 Operationen
• 3. innere for-Schleife : i = 0, 8, 16, 24, 32, ... dh N/8 operationen
• 4. innere for loop: i = 0, 16, 32, 48, 64, ... dh N/16 Operationen
• usw.

N/2 + N/4 + N/8 + N/16 + ... = N(1/2 + 1/4 + 1/8 + 1/16 ...) = N

https://en.wikipedia.org/wiki/1/2_%2B_1/4_%2B_1/8_%2B_1/16_%2B_%E2%8B%AF