Notazione Big-Oh per un singolo ciclo while che copre due metà di un array con due iterator vars

Question

Cercando di rispolverare la comprensione del Big-O per un test (Una comprensione di base del Big-O richiesta ovviamente) Sto arrivando e stava facendo alcuni problemi di pratica nel mio libro.

Mi hanno dato il seguente frammento

public static void swap(int[] a) 
{ 
    int i = 0; 
    int j = a.length-1; 

    while (i < j) 
    { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
     i++; 
     j--; 
    } 
} 

abbastanza facile da capire che penso. Ha due iteratori che coprono metà della matrice con una quantità fissa di lavoro (che penso li tocchi entrambi a O (n/2))

Pertanto O (n/2) + O (n/2) = O (2n/2) = O (n)

Ora, per favore perdonami, poiché questa è la mia attuale comprensione e questo è stato il mio tentativo di risolvere il problema. Ho trovato molti esempi di big-o online ma nessuno che è abbastanza come questo in cui gli iteratori incrementano e modificano l'array praticamente nello stesso tempo.

Il fatto che abbia un ciclo mi fa pensare che sia O (n) comunque.

Qualcuno mi dispiacerebbe chiarire questo per me?

Grazie

Answer 1

Il fatto che ha un ciclo mi sta facendo che sia O (n) in ogni caso.

Questo è corretto. Non perché sta creando un ciclo, ma perché è un ciclo che dipende dalla dimensione dell'array di un fattore costante: la notazione O grande ignora qualsiasi fattore costante. O(n) significa che l'unica influenza sull'algoritmo si basa sulla dimensione dell'array. Che in realtà ci vuole la metà di quel tempo, non importa per il big-O.

In altre parole: se il vostro algoritmo prende tempo n+X, Xn, Xn + Y saranno tutti scendere a O-grande O(n).

Prende differente se la dimensione del ciclo viene cambiata diverso da un fattore costante, ma come una funzione logaritmica o esponenziale di n, ad esempio se la dimensione è 100 e loop è 2, la dimensione è 1000 e loop è 3, la dimensione è 10000 e il ciclo è 4. In tal caso, sarebbe, ad esempio, O(log(n)).

Sarebbe anche diverso se il ciclo fosse indipendente dalla dimensione. Ad esempio, se si eseguono sempre il ciclo 100 volte, indipendentemente dalla dimensione del ciclo, l'algoritmo sarà O(1) (ad esempio, opererà in un tempo costante).

Io vorrei sapere se l'equazione mi è venuta arrivare era da qualche parte nel ballpark di essere corretto.

Sì. Infatti, se l'equazione finisce per essere una forma di n * C + Y, dove C è una costante e Y è un altro valore, il risultato è O(n), indipendentemente dal fatto vedere è maggiore di 1 o inferiori 1.

Answer 2

Hai ragione per il ciclo. Loop determinerà il Big O. Ma il ciclo funziona solo per metà della matrice.

Quindi è. 2 + 6 * (n/2)

Se rendiamo n molto grande, altri numeri sono veramente piccoli. Quindi non contano. Quindi è O (n).

Diciamo che stai eseguendo 2 loop separati. 2 + 6 * (n/2) + 6 * (n/2). In tal caso sarà di nuovo O (n).

Ma se eseguiamo un ciclo annidato. 2+ 6 * (n * n). Quindi sarà O (n^2)

Rimuovere sempre le costanti e fare i conti. Hai avuto l'idea.

Answer 3

Come j-i diminuisce di 2 unità su ogni iterazione, N/2 di esse vengano prese (supponendo N=length(a)).

Quindi il tempo di esecuzione è effettivamente O(N/2). E O(N/2) è strettamente equivalente a O(N).