Qual è la differenza tra & # 920; (n) e O (n)?

Question

A volte vedo & # 920; (n) con lo strano & # 920; simbolo con qualcosa nel mezzo, e talvolta solo O (n). È solo pigrizia di battitura perché nessuno sa come digitare questo simbolo o significa qualcosa di diverso?

Answer 1

Breve spiegazione:

  

Se un algoritmo è di & # 920; (g (n)), significa che il tempo di esecuzione dell'algoritmo man mano che n (dimensione dell'input) diventa più grande è proporzionale a g (n).

     

Se un algoritmo è di O (g (n)), significa che il tempo di esecuzione dell'algoritmo man mano che n diventa più grande è al massimo proporzionale a g (n).

Normalmente, anche quando le persone parlano di O (g (n)) in realtà significano & # 920; (g (n)) ma tecnicamente, c'è una differenza.

---

Più tecnicamente:

O (n) rappresenta il limite superiore. & # 920; (n) significa limite stretto. & # 937; (n) rappresenta il limite inferiore.

  

    

f (x) = & # 920; (g (x)) iff f (x) =     O (g (x)) ef (x) = & # 937; (g (x))

  

Fondamentalmente quando diciamo che un algoritmo è di O (n), è anche O (n ² ), O (n ^1000000 ), O (2 ⁿ ), ... ma un algoritmo & # 920; (n) è non & # 920; (n ² ).

In effetti, poiché f (n) = & # 920; (g (n)) significa che valori sufficientemente grandi di n, f (n) possono essere associati a c ₁ g (n ) ec ₂ g (n) per alcuni valori di c ₁ ec ₂ , ovvero il tasso di crescita di f è asintoticamente uguale a g : g può essere un limite inferiore e e un limite superiore di f. Ciò implica che f può essere anche un limite inferiore e un limite superiore di g. Di conseguenza,

  

f (x) = & # 920; (g (x)) iff g (x) = & # 920; (f (x))

Allo stesso modo, per mostrare f (n) = & # 920; (g (n)), è sufficiente mostrare g è un limite superiore di f (cioè f (n) = O (g (n))) e f è un limite inferiore di g (cioè f (n) = & # 937; (g (n)) che è esattamente la stessa cosa di g (n) = O (f (n))). In modo conciso,

  

f (x) = & # 920; (g (x)) iff f (x) = O (g (x)) e g (x) = O (f (x))

---

Esistono anche notazioni little-oh e little-omega ( & # 969; ) che rappresentano i limiti inferiori superiori e inferiori di una funzione.

Per riassumere:

  

f (x) = O (g (x)) (big-oh) significa che   il tasso di crescita di f (x) è   asintoticamente minore o uguale   a al tasso di crescita di g (x) .

     

f (x) = & # 937; (g (x)) (big-omega) significa   che il tasso di crescita di f (x) è   asintoticamente maggiore di o   uguale a il tasso di crescita di g(x)

     

f (x) = o (g (x)) (little-oh) significa che   il tasso di crescita di f (x) è   asintoticamente inferiore a il   tasso di crescita di g (x) .

     

f (x) = & # 969; (g (x)) (little-omega) significa   che il tasso di crescita di f (x) è   asintoticamente maggiore di il   tasso di crescita di g(x)

     

f (x) = & # 920; (g (x)) (theta) significa che   il tasso di crescita di f (x) è   asintoticamente uguale a il   tasso di crescita di g(x)

Per una discussione più dettagliata, puoi leggere la definizione su Wikipedia o consultare un libro di testo classico come Introduzione agli algoritmi di Cormen et al.

Answer 2

C'è un modo semplice (un trucco, immagino) per ricordare quale notazione significhi cosa.

Tutte le notazioni Big-O possono essere considerate con una barra.

Quando guardi un & # 937 ;, la barra è in fondo, quindi è un limite inferiore (asintotico).

Quando guardi un & # 920 ;, la barra è ovviamente nel mezzo. Quindi è un limite (asintotico) stretto.

Quando scrivi a mano O, di solito finisci in alto e fai uno squiggle. Pertanto O (n) è il limite superiore della funzione. Ad essere sinceri, questo non funziona con la maggior parte dei caratteri, ma è la giustificazione originale dei nomi.

Answer 3

uno è Big " O "

uno è Big Theta

http://en.wikipedia.org/wiki/Big_O_notation

Big O significa che il tuo algoritmo verrà eseguito in non più passaggi rispetto all'espressione data (n ^ 2)

Big Omega significa che il tuo algoritmo verrà eseguito in non meno passaggi rispetto all'espressione data (n ^ 2)

Quando entrambe le condizioni sono vere per la stessa espressione, puoi usare la grande notazione theta ....

Answer 4

Piuttosto che fornire una definizione teorica, che sono già meravigliosamente riassunti qui, farò un semplice esempio:

Supponiamo che il tempo di esecuzione di f (i) sia O (1) . Di seguito è riportato un frammento di codice il cui runtime asintotico è & # 920; (n) . sempre chiama la funzione f (...) n volte. Sia il limite inferiore che quello superiore sono n.

for(int i=0; i<n; i++){
    f(i);
}

Il secondo frammento di codice in basso ha il runtime asintotico di O (n) . Chiama la funzione f (...) al massimo n volte. Il limite superiore è n, ma il limite inferiore potrebbe essere & # 937; (1) o & # 937; (log (n)) , a seconda di ciò che accade all'interno f2 (i) .

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}

Answer 5

Theta è un modo abbreviato di riferirsi a una situtazione speciale in cui la grande O e Omega sono uguali.

Quindi, se si rivendica Il Theta è espressione q , allora stanno anche necessariamente sostenendo che Big O è espressione q e Omega è espressione q .

---

Analogia approssimativa:

Se: Theta afferma: "Quell'animale ha 5 zampe." quindi segue che: Big O è vero ("L'animale ha una zampa inferiore o uguale a 5".) e Omega è vero (" Quell'animale ha più o uguale a 5 zampe. & Quot;)

È solo un'analogia approssimativa perché le espressioni non sono necessariamente numeri specifici, ma invece funzioni di diversi ordini di grandezza come log (n), n, n ^ 2, (ecc.).

Answer 6

Una chart potrebbe semplificare le risposte precedenti per capire:

& # 920; -Notazione - Stesso ordine | Notazione O - Limite superiore

In inglese,

A sinistra, si noti che esiste un limite superiore e un limite inferiore entrambi dello stesso ordine di grandezza (ovvero g (n) ). Ignora le costanti e se il limite superiore e il limite inferiore hanno lo stesso ordine di grandezza, si può validamente dire f (n) = & # 920; (g (n)) o f (n) è in grande theta di g (n) .

Cominciando con la destra, l'esempio più semplice, sta dicendo che il limite superiore g (n) è semplicemente l'ordine di grandezza e ignora la costante c (proprio come tutta la notazione big O fa).

Answer 7

f (n) appartiene a O (n) se esiste k positivo come f (n) < = k * n

f (n) appartiene a & # 920; (n) se esiste k1 , k2 positivo come k1*n<=f(n)<=k2*n

Articolo di Wikipedia su Big O Notation

Answer 8

  

Conclusione: consideriamo big O, big & # 952; e grande & # 937; come la stessa cosa.

     

Perché? Dirò il motivo di seguito:

     

In primo luogo, chiarirò un'affermazione sbagliata, alcune persone pensano che ci preoccupiamo solo della peggior complessità temporale, quindi usiamo sempre big O anziché big & # 952 ;. Dirò che quest'uomo è una cazzata. Il limite superiore e inferiore sono usati per descrivere una funzione, non per descrivere la complessità temporale. La funzione del tempo peggiore ha il limite superiore e inferiore; anche la funzione miglior tempo ha il suo limite superiore e inferiore.

     

Per spiegare chiaramente la relazione tra grande O e grande & # 952; spiegherò prima la relazione tra grande O e piccola o. Dalla definizione, possiamo facilmente sapere che piccola o è un sottoinsieme di grande O. Ad esempio & # 65306;

T (n) = n ^ 2 + n, possiamo dire T (n) = O (n ^ 2), T (n) = O (n ^ 3), T (n) = O (n ^ 4). Ma per la piccola o, T (n) = o (n ^ 2) non soddisfa la definizione di piccola o. Quindi solo T (n) = o (n ^ 3), T (n) = o (n ^ 4) sono corretti per la piccola o. Il ridondante T (n) = O (n ^ 2) è cosa? È grande & # 952 ;!

  

Generalmente, diciamo che O grande è O (n ^ 2), a malapena a dire T (n) = O (n ^ 3), T (n) = O (n ^ 4). Perché? Perché consideriamo la grande O come grande & # 952; inconsciamente.

     

Allo stesso modo, consideriamo anche grandi & # 937; più grande & # 952; inconsciamente.

     

In una parola, grande O, grande & # 952; e grande & # 937; non sono la stessa cosa dalle definizioni, ma sono la stessa cosa nella nostra bocca e nel cervello.

Answer 9

Utilizzo dei limiti

Consideriamo f (n) > 0 e g (n) > 0 per tutti i n . Va bene considerare questo, perché l'algoritmo reale più veloce ha almeno un'operazione e ne completa l'esecuzione dopo l'avvio. Questo semplifica il calcolo, perché possiamo usare il valore ( f (n) ) invece del valore assoluto ( | f (n) | ).

1. f (n) = O (g (n))

   Generale:

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞   g(n)
   

   Per g (n) = n :

             f(n)     
   0 ≤ lim ──────── < ∞
       n➜∞    n
   

   Esempi:

       Expression               Value of the limit
   ------------------------------------------------
   n        = O(n)                      1
   1/2*n    = O(n)                     1/2
   2*n      = O(n)                      2
   n+log(n) = O(n)                      1
   n        = O(n*log(n))               0
   n        = O(n²)                     0
   n        = O(nⁿ)                     0
   

   Controesempi:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ O(log(n))                 ∞
   1/2*n    ≠ O(sqrt(n))                ∞
   2*n      ≠ O(1)                      ∞
   n+log(n) ≠ O(log(n))                 ∞
   

2. f (n) = & # 920; (g (n))

   Generale:

             f(n)     
   0 < lim ──────── < ∞
       n➜∞   g(n)
   

   Per g (n) = n :

             f(n)     
   0 < lim ──────── < ∞
       n➜∞    n
   

   Esempi:

       Expression               Value of the limit
   ------------------------------------------------
   n        = Θ(n)                      1
   1/2*n    = Θ(n)                     1/2
   2*n      = Θ(n)                      2
   n+log(n) = Θ(n)                      1
   

   Controesempi:

       Expression                Value of the limit
   -------------------------------------------------
   n        ≠ Θ(log(n))                 ∞
   1/2*n    ≠ Θ(sqrt(n))                ∞
   2*n      ≠ Θ(1)                      ∞
   n+log(n) ≠ Θ(log(n))                 ∞
   n        ≠ Θ(n*log(n))               0
   n        ≠ Θ(n²)                     0
   n        ≠ Θ(nⁿ)                     0