Notatia W (Omega mare)



Notatia W (Omega mare)

Notatia W (omega mare) precizeaza o margine asimptotica inferioara.

Pentru o functie data g(n), prin W(g(n)) se precizeaza multimea functiilor

= [2.3.4.a]

Fig. 2.3.d Reprezentarea lui f(n)=W(g)n))

  • Teorema: Pentru oricare doua functii f(n) si g(n) , f(n) =
    daca si numai daca f(n) = O(g(n)) si f(n) = .[2.3.4.b]

Spre exemplu s-a demonstrat ca pentru orice valori ale constantelor a, b, c cu a > 0 . De aici rezulta imediat ca .

Deoarece notatia W descrie o limita inferioara, atunci cand este utilizata
pentru a margini cazul cel mai favorabil de executie al unui algoritm, prin implicatie ea margineste inferior orice intrare arbitrara a algoritmului.













Copyright © Contact | Trimite referat


Ultimele referate adaugate
Mihai Beniuc
   - Mihai beniuc - „poezii"
Mihai Eminescu Mihai Eminescu
   - Mihai eminescu - student la berlin
Mircea Eliade Mircea Eliade
   - Mircea Eliade - Mioara Nazdravana (mioriţa)
Vasile Alecsandri Vasile Alecsandri
   - Chirita in provintie de Vasile Alecsandri -expunerea subiectului
Emil Girlenu Emil Girlenu
   - Dragoste de viata de Jack London
Ion Luca Caragiale Ion Luca Caragiale
   - Triumful talentului… (reproducere) de Ion Luca Caragiale
Mircea Eliade Mircea Eliade
   - Fantasticul in proza lui Mircea Eliade - La tiganci
Mihai Eminescu Mihai Eminescu
   - „Personalitate creatoare” si „figura a spiritului creator” eminescian
George Calinescu George Calinescu
   - Enigma Otiliei de George Calinescu - geneza, subiectul si tema romanului
Liviu Rebreanu Liviu Rebreanu
   - Arta literara in romanul Ion, - Liviu Rebreanu











Scriitori romani