Algoritmo complessità

Question

Ho riscontrato questo problema "Implementare questo metodo per restituire la somma dei due numeri più grandi in un determinato array."

ho risolto in questo modo:

public static int sumOfTwoLargestElements(int[] a) { 

    int firstLargest = largest(a, 0, a.length-1); 

    int firstLarge = a[firstLargest]; 
    a[firstLargest] = -1; 

    int secondLargest = largest(a, 0, a.length-1); 

    return firstLarge + a[secondLargest]; 
} 

private static int largest(int s[], int start , int end){ 

    if (end - start == 0){ 

     return end; 
    } 


    int a = largest(s, start, start + (end-start)/2) ; 
    int b = largest(s, start + (end-start)/2+1 , end); 
    if(s[a] > s[b]) { 

     return a; 
    }else { 

     return b; 
    } 

} 

Spiegazione: ho implementato un metodo 'largeset'. Questo metodo è responsabile per ottenere il numero più grande in un determinato array.

Io chiamo i tempi di rimorchio metodo nello stesso array. La prima chiamata otterrà il primo numero più grande. Lo metto da parte in variabile e lo sostituisco con il numero "-1" nell'array. Quindi, chiamo il più grande secondo tempo.

Qualcuno può dirmi qual è la complessità di questo algo? per favore

Answer 1

La complessità temporale dell'algoritmo è O(n).

la complessità di ogni chiamata ricorsiva è in realtà:

f(n) = 2*f(n/2) + CONST 

E 'facile vedere (per induzione) che f(n) <= CONST'*n - e quindi è O(n).

La complessità dello spazio è O(logN) - perché questa è la profondità massima della ricorsione - quindi allocare la memoria O(logN) nello stack di chiamate.

---

(1) Se si utilizza f(n) = 2*n*CONST - CONST si ottiene:

f(n) = 2*f(n/2) + CONST = (h.i.) 2*(2*CONST*n/2 - CONST) + CONST = 
= 2*n*CONST - 2CONST + CONST = 2*n*CONST - CONST 

(Controllo della base viene viene lasciato come esercizio per il lettore)

Answer 2

La complessità dell'algoritmo sarebbe misurata come O(n).

Ma la vera risposta è che il tuo algoritmo è MODO più complesso e più costoso in termini di risorse della macchina di quanto debba essere. Ed è più costoso in termini di qualcuno che legge il tuo codice e capisce cosa sta facendo.

La complessità del vostro algoritmo dovrebbe davvero essere su ordine di:

public static int sumOfTwoLargestElements(int[] a) { 

    //TODO handle case when argument is null, 
    //TODO handle case when array has less than two non-null elements, etc. 

    int firstLargest = Integer.MIN_VALUE; 
    int secondLargest = Integer.MIN_VALUE; 
    for (int v : a) { 
     if (v > firstLargest) { 
      secondLargest = firstLargest; 
      firstLargest = v; 
     } else if (v > secondLargest) secondLargest = v; 
    } 
    //TODO handle case when sum exceeds Integer.MAX_VALUE; 
    return firstLargest + secondLargest; 
} 

Answer 3

Il mio scopo è quello di implementare un algoritmo per 'più grande' con complessità inferiore a O (n). Questo è il motivo per cui non volevo fare il ciclo for. Grazie per le vostre risposte :)

Answer 4

Il reccurence per il metodo 'più grande' è:

 _ 
f(n) = ! 
     ! 1  n = 1 
     ! 2f(n/2) n >=2 
     !_ 

If we experiment some few cases, we notice that 

f(n) = 2^log(n) When n is power of 2  Rq:Log base 2 

Proof: 

By induction, 

f(1) = 2^log(1) = 2^log(2^0) = 1 

We suppose that f(n) = 2^log(n)=n 

We show f(2n) = 2^log(2n)= 2n^log(2)=2n 

f(2n) = 2*f(2n/2) = 2*f(n) 
        = 2*2^log(n) 
        = 2^log(n) + 1 
        = 2^log(n) + log(2^0) 
        = 2^log(2n) 
        = 2n^log(2) by log properties 
        = 2n 
Then f(n) = 2^log(n)=n When n is power of2-smooth function f(2n) < c f(n). it follows smooth function properties that **f(n) = theta of n**