La complessità di una procedura è una funzione di quanti cicli annidati ha?

Question

La complessità di una procedura è una funzione di quanti cicli annidati ha?

#1 da (4 voti)
#2 da (2 voti)

2

Prendi questo esempio

  public static boolean uniqueNumbers(int[] x){
       for(int i = 0; i <x.length; i++){
          for(int j = 0; j <x.length; j++){
              if(i != j && x[i] == x[j])
                  return false;
        }    
    }
    return true;
  }

Il corpo del ciclo eseguirà x.length volte per il ciclo con indice i . Il ciclo interno con indice j eseguirà anche x.length volte, dando una complessità di O(n^2) dove n = x.length .

Come altro esempio

public static int targetSearch(int[] x, int target){
     for(int i = 0; i < x.length; i++){
        if(x[i] == target)
          return i;
     }
     return -1;
 }

Il corpo del ciclo eseguirà x.length di volte poiché ha un solo ciclo che dà una complessità di O(n) .

java methods complexity time

posta Adam 06.04.2017 - 11:28

fonte

2 risposte

2

La maggior parte delle volte, il tempo di esecuzione di un metodo (in O grande) dipende dalla quantità di loop che ha. Ma non sempre.

Esempio di contatore trivial:

for(i=1...n)
   for(j=1...n)
       i *= 2

Ovviamente O(n) poiché il ciclo esterno verrà infatti eseguito una sola volta. Questo può essere un esempio banale, ma ci sono molti algoritmi in cui, a seconda di come è iterato e di altre condizioni interne, conducono a limiti inferiori rispetto alla stretta quantità di cicli.

risposta data 06.04.2017 - 12:16

fonte

Leggi altre domande sui tag java methods complexity time

Java copia i parametri del metodo nello stack frame del metodo chiamato? Buona analogia per i pattern MVP e MVC?

score 4 · Accepted Answer

La notazione Big O viene utilizzata per avere un'idea di cosa accadrà al tempo di esecuzione in quanto il numero di elementi da elaborare aumenta. I cicli sono l'esempio più semplice di come qualcosa aumenta in modo moltiplicativo. Il semplice conteggio dei loop per ottenere un numero O di n ^{numero di cicli nidificati} non funzionerà sempre.

Ecco un esempio trival di un grande O n! programma

void nFacRuntimeFunc(int n) {
  for(int i=0; i<n; i++) {
    nFacRuntimeFunc(n-1);
  }
}

ci sono anche algoritmi come la ricerca binaria che sembrano avere cicli annidati, ma in realtà è grande O log ₂ n perché i loop dividono il tuo input con ogni iterazione.

Oltre ai loop di conteggio semplicemente ingenui, devi tenere conto di ciò che i loop stanno facendo per cambiare la dimensione della successiva iterazione.