Creeaza.com - informatii profesionale despre


Cunostinta va deschide lumea intelepciunii - Referate profesionale unice


Acasa » referate » informatica
Notatia O (O mare)

Notatia O (O mare)




Notatia O (O mare)

Notatia O desemneaza marginea asimptotica superioara a unei functii. Pentru o functie data g(n), se defineste O(g(n)) ca si multimea de functii:

O(g(n)) = [2.3.2.a]

Notatia O se utilizeaza pentru a desemna o margine superioara a unei functii in interiorul unui factor constant.




Pentru toate valorile n superioare lui n0 , valoarea functiei f(n) este pe sau dedesubtul lui g(n) (fig.2.3.b ).


Fig.2.3.b. Reprezentarea lui f(n) = O(g(n))

Pentru a preciza ca o functie f(n) este membra a lui O(g(n)) se utilizeaza notatia f(n) = O(g(n)).

Faptul ca f(n) este Q(g(n)) implica ca  f(n) = O(g(n)) deoarece notatia Q este mai puternica decat notatia O. Formal acest lucru se precizeaza prin relatia [2.3.2.b].

Q(g(n)) O(g(n))  

In consecinta, deoarece s-a demonstrat faptul ca orice functie patratica  a n 2 + b n + c , a > 0 este Q(n 2 , in baza relatiei [2.3.2.b] rezulta ca aceasta functie este implicit si O(n 2).

Este surprinzator faptul ca din aceleasi considerente, functia liniara a n  + b este de asemenea O(n 2), lucru usor de verificat daca se alege  c = a + | b | si n0 = 1.

Notatia O este de obicei cea mai utilizata in aprecierea timpului de executie al algoritmilor respectiv a performantei acestora.

Ea poate fi uneori apreciata direct din inspectarea structurii algoritmului, spre exemplu existenta unei bucle duble conduce imediat la o margine de ordinul O(n 2)

Deoarece notatia O descrie o margine superioara, cand este utilizata pentru a margini cazul cel mai defavorabil de executie al unui algoritm, prin implicatie ea margineste superior comportamentul algoritmului in aceeasi masura pentru orice intrare.

In cazul notatiei Q lucrurile difera.

o      Spre exemplu, daca Q(n2 margineste superior cel mai defavorabil timp de executie al unui algoritm de sortare prin insertie, aceasta nu inseamna ca Q(n2 margineste orice intrare.

o      Astfel, daca intrarea este gata sortata, algoritmul dureaza un timp proportional cu Q(n)

Tehnic vorbind, afirmatia ca timpul de executie al unui algoritm de sortare este O(n2) constituie un abuz de limbaj.

Corect: indiferent de configuratia intrarii de dimensiune n, pentru orice valoare a lui n timpul de executie al algoritmului pentru setul corespunzator de intrari este O(n2).

Cele mai obisnuite ordine de marime ale notatiei O se afla in relatiile de ordine prezentate in [2.3.2.c], iar reprezentarea lor grafica la scara logaritmica apare in fig.2.3.c.

O(1) < O(log  n) < O(n) < O(n log n) < O(n2) < O(n3) <
 < O(2
n) < O(10 n) < O( n ! ) < O(n n)                       [2.3.2.c]


Fig. 2.3.c. Ordine de marime ale notatiei O


In acelasi context in [2.3.2.d] se prezinta cateva sume intregi utile care sunt frecvent utilizate in calculul complexitatii algoritmilor.

[2.3.2.d]






Politica de confidentialitate







.com Copyright © 2022 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 Proiect didactic Clasa: a-IX-a, Luarea deciziilor
 PROIECT DIDACTIC 3-5 ani dezvoltarea limbajului si a comunicarii orale - „Cine face, ce face”
 PROIECT MOTOR ASINCRON - Determinarea parametrilor schemei echivalente si a caracteristicilor de functionare in regim stabilizat de la gol la sarcina
 TEMA DE PROIECTARE - arbore de masina rotativa

Lucrari de diploma

vezi toate lucrarile de diploma
 PROIECT DE DIPLOMA CHIRURGIE ORO-MAXILO-FACIALA - SUPURATIILE LOJELOR PROFUNDE DE ETIOLOGIE ODONTOGENA
 Relatiile diplomatice dintre Romania si Austro- Ungaria din a doua jumatate a secolului al XIX-lea
 LUCRARE DE DIPLOMA MANAGEMENT - MANAGEMENTUL CALITATII APLICAT IN DOMENIUL FABRICARII BERII. STUDIU DE CAZ - FABRICA DE BERE SEBES
 Lucrare de diploma tehnologia confectiilor din piele si inlocuitor - proiectarea constructiv tehnologica a unui produs de incaltaminte tip cizma scurt

Lucrari licenta

vezi toate lucrarile de licenta
 Lucrare de licenta contabilitate si informatica de gestiune - politici si tratamente contabile privind leasingul (ias 17). prevalenta economicului asupra juridicului
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta - cercetare si analiza financiara asupra deseurilor de ambalaje la sc.ambalaje sa
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Atestat la informatica cu tema “gestionarea unui magazin de confectii”
 Proiect atestat electrician constructor - tehnologia montarii instalatiilor electrice interioare
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 ATESTAT PROFESIONAL TURISM SI ALIMENTATIE PUBLICA, TEHNICIAN IN TURISM

Proiectii pe un plan in grafica 3D
SISTEME INFORMATIONALE SI SISTEME INFORMATICE IN GESTIUNEA ORGANIZATIILOR
FUNCTII RTK, Functii de gestionare a timpului, a semafoarelor, a cutiilor postale, a mesajelor
REALIZAREA SISTEMELOR INFORMATICE IN ABORDAREA OBIECTUALA CONFORM R.U.P. ( Retional Unified Process )
DE LA INFORMATICA CLASICA LA INFORMATICA UTILIZATORULUI FINAL
SOFT IMOBILIAR
OFERTA COMERCIALA DE EXPORT A FIRMEI 'BitDefender S.R.L.”
Sumator zecimal pe principiul propagarii seriale a transportului





Termeni si conditii
Contact
Creeaza si tu