Complessità dell'algoritmo

Qual è la complessità data per il seguente problema è O (n). Non dovrebbe essere O (n^2)? Questo perché il ciclo esterno è O (n) e l'interno è anche O (n), quindi n * n = O (n^2)?Complessità dell'algoritmo

Il foglio di risposta di questa domanda indica che la risposta è O (n). Come è possibile?

public static void q1d(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n; j++) { 
      count++; 
     } 
    } 
}

La complessità per il seguente problema è O (n^2), come si può ottenere che? Qualcuno può elaborare per favore?

public static void q1E(int n) { 
    int count = 0; 
    for (int i = 0; i < n; i++) { 
     count++; 
     for (int j = 0; j < n/2; j++) { 
      count++; 
     } 
    } 
}

Grazie

fonte

2012-01-17 Harminder

Penso che quello superiore sia O (n^2). E che dubbio hai sul secondo? – WordsWorth

Ciò significa che la risposta fornita dal mio professore è errata hmm. – Harminder

sembra che il foglio delle risposte contenga errori. – Zohaib

La complessità sia codice è O (n * n)

PRIMO

Il ciclo esterno esegue n volte e il ciclo interno varia da 0 to n-1 volte

quindi

total = 1 + 2 + 3 + 4 ... + n

che se si aggiunge il arithmetic progression è n * (n + 1)/2 è O(n*n)

SECONDO

Il ciclo esterno viene eseguito n volte e il ciclo interno varia da 0 to n-1/2 volte

così

total = 1 + 1/2 + 3/2 + 4/2 ... + n/2

che se si aggiunge la progressione aritmetica è n * (n + 1)/4 è anche O(n*n)

fonte

2012-01-17 05:28:26

Quindi se n/2 è ancora uguale a o (n)? Ma l'iterazione per il ciclo interno è la metà del ciclo esterno che fa qualche differenza? – Harminder

@ user1085135: 'O (n)' ha il significato 'lineare'. Non importa quale costante si moltiplica per, ciò che importa è che ** è ** lineare – zerkms

Il primo esempio è O(n^2), così sembra di aver fatto un errore. Per calcolare (informalmente) il secondo esempio, possiamo fare n * (n/2) = (n^2)/2 = O(n^2). Se questo non ha senso, è necessario andare e rispolverare il significato di qualcosa che è O(n^k).

fonte

2012-01-17 05:29:13 Yuushi

Primo caso è sicuramente O(n^2)

Il secondo è O(n^2) pure perché si omette le costanti quando calcolare grande O

fonte

2012-01-17 05:31:20 zerkms

Il foglio di risposta è sbagliata, il primo algoritmo è chiaramente O (n^2).

La notazione Big-Oh è "worst case", quindi quando si calcola il valore Big-Oh, generalmente ignoriamo le moltiplicazioni/divisioni per le costanti.

Detto questo, il tuo secondo esempio è anche O (n^2) nel caso peggiore perché, sebbene il ciclo interno sia "solo" 1/2 n, il n è il chiaro fattore di delimitazione. In pratica il secondo algoritmo sarà inferiore alle operazioni di O (n^2) - ma Big-Oh è inteso come una misura del "caso peggiore" (cioè il limite massimo), quindi il numero esatto di operazioni viene ignorato a favore di concentrandosi su come l'algoritmo si comporta come n si avvicina all'infinito.

fonte

2012-01-17 05:33:03 debracey

Il secondo algoritmo non sarà inferiore a O (n^2), è * precisamente * O (n^2). Sospetto che tu non sia abbastanza chiaro su cosa significhi "O (n^2)". Significa che quando 'n' si avvicina all'infinito, il tempo di esecuzione aumenta per l'algoritmo per due valori di' n' è proporzionale alla differenza tra quei valori 'n' al quadrato. –

No. In pratica, la complessità temporale attuale dell'algoritmo sarà leggermente inferiore a O (n^2). Tuttavia, poiché Big-Oh è un limite massimo, diciamo che è O (n^2). Hai ragione sul fatto che il fattore 'n/2' è chiaramente limitato da n - come ho indicato nella mia risposta. Esistono altre misure di delimitazione (es. Big-Theta) che calcolano il fattore di delimitazione in modo diverso. – debracey

Perché pensi che la complessità temporale attuale dell'algoritmo sarà inferiore a O (n^2)? Suppongo che sarà * precisamente * O (n^2) perché la complessità dell'algoritmo * precisamente * corrisponde alla * definizione * di O (n^2). Se non è * esattamente * O (n^2), allora niente è. Diciamo * che è O (n^2) perché ** è ** O (n^2). Sembra che tu voglia renderlo confuso, confuso e impreciso quando è assolutamente cristallino. –

Entrambi sono O(n^2). La tua risposta è sbagliata. Oppure potresti aver scritto la domanda in modo errato.

fonte

2012-07-17 06:53:55 Shashwat

Complessità dell'algoritmo

risposta

Problemi correlati