Cos'è Big O di sqrt (1) + sqrt (2) + ... + sqrt (n)? [duplicare]

Questa è fondamentalmente una domanda di matematica, potrebbe essere meglio su "Computer Science" stackexchange o anche SO. Ma immagino che puoi aspettarti che i programmatori lo sappiano, e Programmers non è solo per le domande "Soft", quindi forse è ben posizionato qui.

In ogni modo.

Sulla base delle risposte finora, credo che Phillip Kendall abbia interpretato erroneamente la tua domanda. Pensa che tu stia chiedendo "qual è la complessità computazionale della valutazione di questa somma". Stai chiedendo. "Qual è il tasso di crescita di questa somma".

Esistono diverse tecniche per stimare i tassi di crescita delle serie. Uno piuttosto generale è il metodo integrale , che in pratica lo trasforma in un problema di calcolo. L'idea è che prendere una serie, che sta prendendo i valori secondo una funzione analitica come f(n) = n o f(n) = n^{0.5} , è la stessa cosa, prendendo l'integrale di una funzione "passo" sull'intervallo (continuo) da 1 a n . Poiché la funzione step è limitata da sopra e sotto dalla funzione smooth e la funzione smooth è facile da integrare (o almeno, quando è facile da integrare), questo dà una risposta pulita.

Ad esempio, sai che l'integrale indefinito di x dx è 1/2 x^2 , quindi la somma 1 + 2 + ... + n è O(n^2) .

Nel tuo caso, ti interessa sommare fino a sqrt(n) . L'integrale indefinito di sqrt(x) dx è 2/3 x^{3/2} . Quindi la somma 1 + sqrt(2) + ... + sqrt(n) è O(n^{3/2}) .

Tuttavia, molte persone hanno dimenticato il loro calcolo. In molti casi puoi fare a meno di semplici euristiche per stimare queste cose.

Ad esempio, nella somma 1 + sqrt(2) + ... + sqrt(n) , sai che sqrt(n) è il numero più grande nella somma. E ci sono n numeri nella somma. Così facilmente, puoi vedere che la somma non può superare n * sqrt(n) .

Ora, ti piacerebbe vedere che la somma non può essere molto inferiore. È più difficile vederlo perché le voci all'inizio sono piccole. Tuttavia, qual è il valore di una voce tipica . Prendiamo in considerazione tutti i numeri nella seconda metà. L'ultimo di questi è sqrt(n) e la voce centrale è sqrt(n/2) . Ma sqrt(n/2) può anche essere riscritto sqrt(n) / sqrt(2) . In altre parole, tutte le voci nella seconda metà della sequenza sono all'interno di un fattore sqrt(2) di eachother, quindi per quanto riguarda Big O sono "uguali".

Concretamente, tutti i numeri nella seconda metà della somma sono almeno sqrt(n) / sqrt(2) . E ci sono n/2 di quei numeri. Quindi la somma è almeno n * sqrt(n) / (2 sqrt(2)) , e quella funzione è anche O(n^{3/2}) .

Quindi sappiamo, senza calcolo, che il tasso di crescita è all'interno di un fattore costante di n^{3/2} .

Mi piace questo modo di affrontare il problema perché promuove il buon pensiero ingegneristico. Quando un problema è difficile da risolvere direttamente, è opportuno concentrarsi sul caso tipico. Spesso, se realizzi qualcosa che funziona bene in genere, ciò è abbastanza buono nella pratica. È anche vero in Scienza. A volte, la costante esatta in alcune formule è molto importante ed è necessario utilizzare potenti strumenti come il calcolo per trovarlo. Ma più comunemente, le persone si preoccupano solo del quadro generale e il calcolo può oscurarlo con un'attenzione particolare alle soluzioni a forma chiusa e alle costanti esatte. Molte volte, se riesci a capire il caso tipico, questo ti dà abbastanza informazioni per risolvere il problema generale.

La complessità è ovviamente la somma di sqrt (i), per i = 1 a n. Questo tipo di somma è solitamente abbastanza difficile da calcolare in forma chiusa. Come approssimazione non si calcola la somma, ma l'integrale di sqrt (i) su un intervallo di larghezza n (dato che si sommano n valori), e se non si ha una buona ragione per scegliere qualcosa di diverso, si prenderà il integrale di sqrt (x) per x da 0,5 a n + 0,5.

Ora devi ricordare la tua matematica; l'integrale di x ^ k è x ^ (k + 1) / (k + 1), e l'integrale di sqrt (x) = x ^ (1/2) è x ^ (3/2) / (1.5), quindi l'integrale da 0.5 a n + 0.5 è circa (n + 0.5) ^ (3/2) / (1.5), rendendolo O (n ^ 3/2).

(Questa non è davvero una prova, ma con una certa esperienza sai che potresti provarlo, se necessario. E dà non solo O (n), ma anche una stima decente, quante volte viene chiamato foo () , circa n ^ 1,5 / 1,5 volte).