Qual è la differenza tra limite inferiore e limite stretto?

Question

Con il riferimento di questa answer , che cos'è Theta (limite stretto)?

Omega ha un limite inferiore, ben compreso, il tempo minimo che un algoritmo può richiedere. E sappiamo che Big-O è per limite superiore, significa che il tempo massimo che un algoritmo può richiedere. Ma non ho idea del Theta.

Answer 1

Big O è il limite superiore, mentre Omega è il limite inferiore. Theta richiede sia Big O sia Omega, quindi è per questo che viene chiamato limite stretto (deve essere sia il limite superiore che inferiore).

Ad esempio, un algoritmo che impiega Omega(n log n) richiede almeno n log n tempo, ma non ha limiti superiori. Un algoritmo che prende Theta(n log n) è di gran lunga preferenziale poiché richiede almeno <=> (Omega n log n) e non più di <=> (Big O n log n ).

Answer 2

& # 920; -notation (notazione theta) è chiamato stretto perché è più preciso di O-notation e & # 937; -notation (notazione omega).

Se fossi pigro, potrei dire che la ricerca binaria su un array ordinato è O (n ² ), O (n ³ ) e O (2 < sup> n ) e sarei tecnicamente corretto in ogni caso. Questo perché la notazione O specifica solo un limite superiore e la ricerca binaria è limitata nella parte alta da tutte queste funzioni, ma non molto da vicino. Queste stime pigre sarebbero inutili .

& # 920; -notation risolve questo problema combinando O-notation e & # 937; -notation. Se dico che la ricerca binaria è & # 920; (log n), ciò ti dà informazioni più precise. Ti dice che l'algoritmo è limitato su entrambi dalla funzione data, quindi non sarà mai significativamente più veloce o più lento di quanto dichiarato.

Answer 3

Se hai qualcosa che è O (f (n)) significa che ci sono k , g (n) tale che f (n) & # 8804; k g (n) .

Se hai qualcosa che è & # 937; (f (n)) significa che ci sono k , g (n) tale che f (n) & # 8805; k g (n) .

E se hai qualcosa con O (f (n)) e & # 937; (f (n)) , quindi è & # 920; (f (n) .

L'articolo di Wikipedia è decente, anche se un po 'denso.

Answer 4

Limite superiore asintotico significa che un determinato algoritmo viene eseguito durante il periodo di tempo massimo, a seconda del numero di input.

Prendiamo un algoritmo di ordinamento come esempio. Se tutti gli elementi di un array sono in ordine decrescente, quindi per ordinarli, ci vorrà un tempo di esecuzione di O(n), mostrando la complessità del limite superiore. Se l'array è già ordinato, il valore sarà O(1).

In generale, O-notation viene utilizzato per la complessità del limite superiore.

---

Limite stretto asintoticamente (c ₁ g (n) & # 8804; f (n) & # 8804; c ₂ g (n)) mostra la complessità media legata per una funzione, avente un valore tra i limiti associati (limite superiore e limite inferiore), dove c ₁ e c ₂ sono costanti.

Answer 5

Le frasi tempo minimo e tempo massimo sono un po 'fuorvianti qui. Quando parliamo di grandi notazioni O, non è il momento effettivo a cui siamo interessati, è come aumenta il tempo quando le dimensioni dell'input aumentano. Di solito è il momento medio o peggiore di cui stiamo parlando, non il caso migliore , che di solito non ha senso nel risolvere i nostri problemi.

Utilizzo della ricerca di array nella risposta accettata all'altra domanda come esempio. Il tempo necessario per trovare un numero particolare nell'elenco delle dimensioni n è n / 2 * some_constant in media. Se la tratti come una funzione f(n) = n/2*some_constant, non aumenta più velocemente di g(n) = n, nel senso indicato da Charlie. Inoltre, non aumenta neanche più lentamente di g(n). Quindi, f(n) è in realtà sia un limite superiore che un limite inferiore di <=> nella notazione Big-O, quindi la complessità della ricerca lineare è esattamente n , che significa che è Theta (n).

A questo proposito, la spiegazione nella risposta accettata all'altra domanda non è del tutto corretta, che afferma che O (n) è limite superiore perché l'algoritmo può essere eseguito in tempo costante per alcuni input (questo è il nel migliore dei casi ho menzionato sopra, che non è proprio quello che vogliamo sapere sul tempo di esecuzione).

Answer 6

  

Se fossi pigro, potrei dire che lo è la ricerca binaria su un array ordinato   O (n2), O (n3) e O (2n), e sarei tecnicamente corretto in ogni   caso.

Possiamo usare la notazione o (" little-oh ") per indicare un limite superiore che non è asintoticamente stretto. Sia big-oh che little-oh sono simili. Ma big-oh è probabilmente usato per definire il limite superiore asintoticamente stretto.

Answer 7

Precisamente il limite inferiore o $ \ omega $ bfon f (n) indica l'insieme di funzioni asintoticamente inferiori o uguali a f (n) cioè U      g (n) # 8804 &; cf (n) $ \ per tutti $ `un & # 8805; n' Per alcuni c, n '$ \ in $ $ \ Bbb {N} $

E il limite superiore o $ \ mathit {O} $ su f (n) indica l'insieme di funzioni che sono assintoticamente maggiori o uguali a f (n) che dice matematicamente,

$ g (n) \ ge cf (n) \ per tutti n \ ge n '$, per alcuni c, n' $ \ in $ $ \ Bbb {N} $.

Ora $ \ Theta $ è l'intersezione dei due scritti sopra

  

$\theta $

Come se un algoritmo fosse come " esattamente $ \ Omega \ left (f (n) \ right $ " quindi è meglio dire che è $ \ Theta \ left (f (n) \ right) $.

Oppure possiamo anche dire che ci dà la velocità effettiva in cui $ \omega $ ci dà il limite più basso.

Answer 8

La differenza di base tra

  

Blockquote

limite superiore asintoticamente e stretto asintoticamente Asym.upperbound indica un determinato algoritmo che può essere eseguito con la massima quantità di tempo a seconda del numero di input, ad esempio in ordine di ordine se tutti gli elementi dell'array (n) sono in ordine decrescente, quindi per ascenderli ci vorrà un tempo di esecuzione di O (n) che mostra la complessità del limite superiore, ma se sono già ordinati allora prenderà ohm (1). Quindi generalmente abbiamo usato & Quot; O & Quot; notazione per complessità del limite superiore.

Asym. limite rilegato mostra ad es. (c1g (n) < = f (n) < = c2g (n)) mostra il limite del limite stretto in modo che la funzione abbia il valore tra due limiti (superiore limite e limite inferiore), dando il caso medio.