Complessità temporale delle coppie in array doppio ciclo

Question

So, che il seguente è: O (n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

Ma, dovrebbe qualcosa di simile count = count + 1; essere presi in considerazione?Per prevedere o creare un'equazione del tempo complessa, o usando la notazione della somma,

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

È un compito ben noto "Verifica dei duplicati" e puoi trovarlo ad esempio in Tim RoughGarden - Algoritmi illuminati_ parte 1_ Le basi- (2017) 42 Pagina. Lasciatemi dire, che come qui così nel libro prendendo l'ultimo indice "I" come $ n= $ "array.length ()" non ha senso, perché allora indice " j "finisce i confini. Ma questo non influisce sul nostro conteggio.

Come sempre principale è scegliere il funzionamento per il conteggio - qui è il suo "conteggio= conteggio + 1". Ovviamente il caso migliore, cioè la minima quantità di operazioni, è $ 0 $ . E custodia peggiore, cioè la massima quantità di operazioni, è la somma (la corretto di conseguenza prendendo indice "I" su $ N-1 $ ) portato da You $ t (n)= 1 + 2 + \ cdots + (n-1)=frac {n (n-1)} {2} $ (consideriamo caso $ n \ GeqStant 2 $ ).

Ora, perché $ \ frac {n (n-1)} {2} \ leqslant \ frac {n \ cdot 2n} {2}= n ^ 2 $ , è facile concludere, quella cassa peggiore $ t (n) \ in o (n ^ 2) $ .

Answer 2

La complessità temporale di un algoritmo dipende dal modello di calcolo.Gli algoritmi vengono solitamente analizzati nella macchina RAM, in cui le operazioni di base sulle parole della macchina (come assegnazione, aritmetica e confronto) costano O O (1)$.Una parola macchina ha lunghezza O O ( egistro n)$, cui $e$ è la dimensione dell'input.

Nel tuo caso, la dimensione dell'input è almeno $e$ (definita come la lunghezza di array), e così count si inserisce in una singola parola macchina.Ciascuna delle operazioni di base nell'algoritmo costa O O (1)$, e così la complessità di tempo globale è Th \ Teta (n^2)$, poiché l'algoritmo esegue questo molte operazioni di base.