Perché la dichiarazione:Il tempo di esecuzione dell'algoritmo A è almeno O (n²) - Perché è privo di significato?
Il tempo di esecuzione di algoritmo A è almeno O (n²)
non ha senso?
Il tempo di esecuzione di algoritmo di ordinamento di inserimento è al massimo O (n²)
è corretto?
Ho provato la rete ma non ho potuto ottenere una buona spiegazione.
ho un'altra domanda:
So che ogni funzione a⋅n + b lineare è O (n) e O (n²). È anche O (n³)?
T(n): durata della Algo A.Abbiamo appena preoccupiamo per il limite superiore e il limite inferiore di T(n) La dichiarazione: T(n) >= O(n^2)
Limite superiore: Perché T(n) >= O(n^2), allora non c'è informazioni su limite superiore di T(n) Limite inferiore: Si supponga f(n) = O(n^2), allora l'istruzione: T(n) >= f(n), ma f(n) potrebbe essere tutto ciò che è "più piccolo" rispetto n^2, Es: constant, n,..., quindi non c'è alcuna conclusione circa limite inferiore di T(n) troppo
=> L'affermazione è priva di significato
+1 Questa è la risposta corretta. – chepner
Una ragione potrebbe essere che un limite inferiore senza limite superiore non è molto utile. "almeno" significa che può essere esponenziale in un caso normale. Se non conosci il limite superiore, probabilmente non puoi usare l'algoritmo in un'applicazione reale perché non puoi sapere se il programma finisce prima dell'universo.
La notazione O grande se utilizzata correttamente indica un limite superiore. Quindi affermare un limite inferiore quando O grande sta abusando della notazione.
Detto questo "senza significato" è una parola forte. È certamente un'informazione utile anche se non è adeguata. Con un po 'più di contesto alla tua domanda potresti ottenere un aiuto migliore.
Grazie per la tua risposta precisa.Se considero l'algoritmo di ordinamento A come Insertion, allora è utile dire "Il tempo di esecuzione dell'algoritmo A è almeno O (n2)?" In questo contesto? – tanmoy
un altro dubbio: qualsiasi funzione lineare an + b è O (n) ed è anche O (n^2). È anche O (n^3)? – tanmoy
Come ho detto, è corretto e significativo stabilire il limite inferiore del tempo di esecuzione, è solo che è inusuale usare la notazione O grande per esso, che di solito è riservata al limite superiore della complessità temporale. Dire "è almeno n2" è più formalmente descritto come (grande) Omega (n^2), che significa "limitato di seguito da n^2 asintoticamente". Quindi non dovresti usare "O (..)" a meno che tu non intenda "delimitato sopra, asintoticamente". http://en.wikipedia.org/wiki/Big_O_notation –
"Il tempo di esecuzione dell'algoritmo A è almeno O (n2)" è equivalente a "Il tempo di esecuzione dell'algoritmo A è Big Omega (n2)", quindi non è privo di significato.
notazione O, in altre parole significa: f (x) appartiene impostato O (g (x)) se f (x) < C * g (x), per tutti C (quelli sono numeri reali)
cioè l'algoritmo non cresce più di una funzione quadratica
non è privo di significato, può essere utilizzata, ad esempio, se non si conosce l'algoritmo esatto, ma certamente sa che richiederà O (n^2) operazioni.
Ad esempio, se non si conosce l'algoritmo di ordinamento, ma si capisce, che per ordinare un array è necessario almeno esaminare ogni elemento, si può dire che "l'ordinamento di un array è almeno O (n) ".
@downvoter: qualche spiegazione? –
Perché a nessuno importa quanto velocemente funzioni nel migliore dei casi, il caso peggiore è importante. Di solito le persone sono interessate a sapere quanto ci vorrà nel peggiore dei casi.
Lascia che sia f(n) il tempo di esecuzione dell'algoritmo.
=> f(n) >= O(n2)
=> f(n) >= 0 , because 0 is a member of set of functions that are O(n2)
Questo è sempre vero per f(n), dal momento che il tempo di esecuzione è sempre non negativo. Quindi, la dichiarazione è ridondante.
O (n^2) è uno scenario nel peggiore dei casi, il che significa che il tempo di esecuzione di A sarà n^2 o più veloce. Se il suo tempo di esecuzione è almeno pari a O (n^2), ciò significa che il tempo di esecuzione più veloce A può avere, è almeno O (n^2). Ciò significa che potrebbe anche essere qualcosa di più lento di O (n^2). Queste affermazioni indicano che A può avere qualsiasi tempo di esecuzione possibile.
So che qualsiasi funzione lineare an + b è O (n) e anche O (n^2). È anche O (n^3)?
Sì, lo è. La notazione O grande indica un'intera collezione di funzioni. Ma dovremmo usarlo per caratterizzare una funzione il più vicino possibile. Mentre è vero che f(n) = an+b è O(n^2) o anche O(n^3), è più preciso dire che f(n) = O(n).
Un'analogia:
L'affermazione è un po 'come dire: "Il tetto della mia casa si trova ad un'altezza che è almeno il livello del suolo" Vero, ma completamente disinformativo.
In quale contesto poni questa domanda? – nhahtdh
Non ha senso perché non è stato fornito alcun algoritmo A. – aqua
Consentire all'algoritmo A l'algoritmo di ordinamento per inserzione. – tanmoy