Qual è la complessità temporale della mia funzione?

Question

iniziato a studiare sulla complessità, sto lottando con questo:

void what(int n) { 
    int i; 
    for (i = 1; i <= n; i++) { 
     int x = n; 
     while (x > 0) 
      x -= i; 
    } 
} 

Bene, la prima per il ciclo è chiaramente O(n). La prima iterazione è O(n), la seconda è O(n/2) .. e come quella log(n) volte credo? Che significa O(n) * O(log(n)) = O(n * log(n)) complexity. Ho capito bene?

Modifica: (non un duplicato) So cosa è Big O. Ho chiesto la valutazione corretta in un caso specifico.

Answer 1

Il ciclo esterno corre n volte.

Per ogni iterazione, i cicli interni vengono eseguiti n/i volte.

Il numero totale di run è:

n + n/2 + n/3 + ... + n/n 

Asintoticamente (ignorando aritmetica intera arrotondamento), questo semplifica come

n * (1 + 1/2 + 1/3 + ... + 1/n) 

Questa serie converge debolmente verso n * log(n).

Quindi la complessità è O (N.log (N)) come previsto.

Answer 2

Il primo ciclo interno viene eseguito n volte
Il secondo ciclo interno viene eseguito n/2 volte
Il terzo ciclo interno viene eseguito n/3 volte
.. L'ultimo viene eseguito una volta

Così n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n).

Questo è n moltiplicato per la somma delle serie armoniche, che non ha una bella rappresentazione di forma chiusa. Ma come mostrato here è O(log(n)). Quindi nel complesso l'algoritmo è O(n log(n))

Answer 3

Tentativo di test e grafica. Il grafico log2 vs log2 sembra abbastanza lineare. Qualcosa tra più di O (n) lineare e meno di O (n * log (n)). "Disegna" le tue conclusioni.

[Edit]

Utilizzando le formule matematiche derivate, la O() calcolato è un limite superiore di O (n * log (n)). Ciò utilizza "frazioni di iterazioni di loop" che aumentano il conteggio di una frazione e non di 1 E.g. Quando n è 6, il conteggio di iterazione è 6 + 3 + 2 + 1,5 + 1,2 + 1 = 14,7 cicli anziché effettivo 6 + 3 + 2 + 2 + 2 + 1 = 16. Questa differenza è relativamente meno significativa al crescere di n, quindi la crescita leggermente inferiore a O (n * log (n)). Quindi, non ignorando il codice usa la matematica intera, abbiamo una domanda molto più stimolante.

---

unsigned long long what(int n) { 
    unsigned long long cnt = 0; 
    int i; 
    for (i = 1; i <= n; i++) { 
    int x = n; 
    while (x > 0) { 
     x -= i; 
     cnt++; 
    } 
    } 
    return cnt; 
} 

void wtest(int n) { 
    unsigned long long cnt = what(n); 
    printf("%d %llu\n", n, cnt); 
    fflush(stdout); 
} 

void wtests(void) { 
    int i = INT_MAX/2 + 1; 
    while (i > 0) { 
    wtest(i); 
    i /= 2; 
    } 
} 

int main(void) { 
    wtests(); 
    return 0; 
} 

uscita

1073741824 23567395117 
536870912 11411566988 
268435456 5519718329 
134217728 2666826555 
67108864 1286897093 
33554432 620190504 
16777216 298466265 
8388608 143418602 
4194304 68802063 
2097152 32947406 
1048576 15746897 
524288 7510048 
262144 3573331 
131072 1695816 
65536 802493 
32768 378537 
16384 177921 
8192 83286 
4096 38803 
2048 17973 
1024 8275 
512 3782 
256 1713 
128 765 
64 337 
32 145 
16 61 
8 24 
4 9 
2 3 
1 1 

Answer 4

In alternativa, utilizzare un cambio variabile y = n - x seguita da Sigma notazione per analizzare il numero di iterazioni del interno while ciclo dell'algoritmo .

I sovrastima sopra, per ogni ciclo while interno, il numero di iterazioni da 1 nei casi in cui n-1 non è un multiplo di i, cioè dove (n-1) % i != 0. Mentre procediamo, assumiamo che (n-1)/i sia un numero intero per tutti i valori di i, quindi sovrastima il numero totale di iterazioni nel ciclo interno while, includendo successivamente il segno di minore o uguale a (i) di seguito. Si procede con l'analisi notazione Sigma:

dove, a (ii), approssimato il n: th harmonic number dall'integrale associato. Quindi, l'algoritmo viene eseguito in O(n·ln(n)), asintoticamente.

---

Lasciando comportamento asintotico e studiare la crescita effettiva dell'algoritmo, siamo in grado di utilizzare i dati di esempio belle di esatto (n,cnt) (dove cnt è il numero di iterazioni interne) coppie da @chux (fare riferimento alla sua risposta) e confronta con il numero stimato di iterazioni dall'alto, ovvero, n(1+ln(n))-ln(n). È evidente che la stima si armonizza perfettamente con il conteggio effettivo, vedere i grafici sottostanti o this snippet for the actual numbers.

---

Infine si noti che se lasciamo n->∞ nella somma su 1/i sopra, la serie risultante è la infinite harmonic series, che è, curiosamente, divergenti. La prova per il secondo fa uso del fatto che in infiniti termini non-zero naturalmente è infinito stesso. In pratica, tuttavia, per un sufficientemente grande ma non infinito n, ln(n) è un'appropriata approssimazione della somma, e questa divergenza non è rilevante per la nostra analisi asintotica qui.

---