Aggiunta di un registro nell'analisi asintotica

Question

Avere un problema che sto cercando di lavorare e apprezzerei molto qualche assistenza! Qual è la complessità temporale di ...

for (int j = 1 to n) {
    k = j;
    while (k < n) {
        sum += a[k] * b[k];
        k += log n;
    }
}

L'esterno per loop funziona n volte. Non sono sicuro di come affrontare k+= log n Nel ciclo interno. Il mio pensiero è che è O (n^2). L'aggiunta del registro (N) a K non sta ottenendo un numero più presente N, ma penso che sia inferiore a O (n*log n). Ovviamente, è solo un'ipotesi e qualsiasi aiuto nel capire come dimostrare che matematicamente sarebbe molto apprezzato!

Answer 1

Puoi trattare log(n) Come costante qui, in un certo senso.

Ogni iterazione del ciclo eseguirà una quantità costante di lavoro (sum+=...; k+=...) un numero di volte uguale a n/log(n). Ci sono n iterazioni del ciclo. Il lavoro totale è quindi n^2 / log(n).

Ogni volta che vedi un sacco di operazioni come così:

 ---------------------b-------------------------
 |O(blah) + O(blah) + O(blah) + O(blah) + O(blah)
 |O(blah) + O(blah) + O(blah) + O(blah)     .
a|O(blah) + O(blah) + O(blah)               .
 |O(blah) + O(blah)                         .
 |O(blah)     .         .         .         .

è a*b * O(blah) - Immagina la piazza (dove ho messo il .S). È una frazione costante di un rettangolo 2D (metà di un rettangolo), da cui il O(a*b).

Nel caso sopra, b =n, a =n/log(n), e O (blah) =O(1)(dal ciclo interno)

Answer 2

Puoi abbastanza facilmente "solo suonare":

Il ciclo esterno ha come hai detto n Passi. Il ciclo interiore ha (k-j) / log n Passi.

Questo è (approssimativamente):

 n
---
\     (n-j)             n*n
/   -------- = ... = ---------
___  (log n)          2*log(n)
j=1

Così è O((n^2)/log(n)) in totale.

Answer 3

Puoi procedere formalmente come quanto segue: