Algorithm Analysis: Frequencies of Execution

1

Attualmente sto leggendo la sezione Analisi degli algoritmi in Algorithms, 4a edizione e sto cercando di capire come l'autore ha calcolato (N ^ 2) / 2 e (N ^ 3) / 6 frequenze di esecuzione nello snippet di codice seguente ( qui è il codice completo):

public class ThreeSum
{
    public static int count(int[] a) {
            int N = a.length;
            int cnt = 0;
            for (int i = 0; i < N; i++) { // <---------------- 1
                for (int j = i+1; j < N; j++) { // <---------- N
                    for (int k = j+1; k < N; k++) { // <------ N^2/2
                        if (a[i] + a[j] + a[k] == 0) { // <--- N^3/6
                            cnt++;  // <---------------------- x
                        }
                    }
                }
            }
            return cnt;
        } 
}

Perché dividere N ^ 2 per 2? Perché dividere N ^ 3 per 6?

    
posta Anthony 17.08.2012 - 00:02
fonte

1 risposta

4

È parte dell'utilizzo di " somme parziali " per determinare le frequenze di esecuzione. La sezione specifica è "Scorciatoie utili" dove mostra quale eventualità esiste per un determinato ordine di termine iniziale in una sequenza.

    
risposta data 17.08.2012 - 00:12
fonte

Leggi altre domande sui tag