Böyük O işarələr sistemi

Böyük O işarə göstəricisi, arqument müəyyən bir dəyərə və ya sonsuzluğa yaxınlaşanda bir funksiyanın məhdudlaşdırıcı davranışını təyin edən riyazi işarədir. Paul Bachmann, Edmund Landau və digərləri tərəfindən icad edilən,** Bachmann-Landau işarəs**i və ya **asimptotik işarə** olaraq adlandırılan işarələr qrupunun üzvüdür.

Kompüter elmlərində böyük O işarəsi, alqoritmlərin, problemin ölçüsü son dərəcə böyük olduğunda dəyişikliyə necə reaksiya verdiyini təsnif etmək üçün istifadə edilir. Analitik sayı nəzəriyyəsində, aritmetik bir funksiyanın asimptotik ölçüsünü böyük sonlu argumentlərdən keçən dəyərlə dəyişdirərkən "baş vermiş səhv" təxmin edilir. Məşhur nümunə, sadə ədədlər teoremində qalığın təxmin edilməsi problemidir.

Böyük O işarəsi, funksiyaları böyümə sürətinə görə xarakterizə edir: eyni böyümə nisbətinə sahib fərqli funksiyalar eyni O işarəsi ilə göstərilə bilər.

**Böyükdür** — (ing. *greater than*, ru. *больше*)

**Böyükdür və ya bərabərdir** (ing. *greater than or egual to*, ru. *больше или равно*) 

Funksiyanın böyümə nisbəti **funksiyanın sırası **(order of the function) olaraq da adlandırıldığından, O hərfi istifadə olunur. Bir funksiyanın böyük O işarəsi baxımından bir tərifi ümumiyyətlə funksiyanın böyümə nisbətinin üst sərhədini təmin edir. Böyük O işarəsi ilə əlaqəli olaraq, asimptotik böyümə dərəcələrində digər sərhəd növlərini müəyyənləşdirmək üçün o, Ω, ω və Θ işarələrindən də istifadə olunur.

Böyük O işarəsi, bənzər proqnozları təmin etmək üçün bir çox sahədə də istifadə olunur.

## Formal tərif
f və g həqiqi ədədlər çoxluğunda təyin olunmuş funksiyadırsa
: f(x)=O(g(x))\text{ olarsa }x\to\infty\,
yalnız və yalnız x'in bütün kifayət qədər böyük dəyərləri üçün, f (x) 'in mütləq dəyərinin mütləq g(x) mütləq dəyəri ilə hasili qədər müsbət M sabiti varsa doğrudur. Yəni, f (x) = O (g (x)) yalnız və yalnız M və x0 müsbət həqiqi ədədlərdirsə 
: |f(x)| \le \; M |g(x)|\text{ bütün }x \ge x_0.
Bir çox baxımdan, ehtimal ki, x dəyişəni sonsuzluğa yaxınlaşnda böyümə surəti
: f(x) = O(g(x)).
O işarəsi eyni zamanda f'in, həqiqi ədəd olan a'nın (ümumiyyətlə, a = 0) yaxınındakı davranışını təsvir etmək üçün istifadə edilə bilər:

f(x)=O(g(x))\text{ olarsa }x\to a\,

Ancaq və ancaq müsbət ədədlər δ və M varsa,

: |f(x)| \le \; M |g(x)|\text{ o zaman ki, } 0 .
Əgər g(x), x dəyərləri a'ya kifayət qədər yaxın olanda 0 deyilsə, bu təriflərin hər ikisi üst limiti istifadə etməklə birləşdirilə bilər:
: f(x)=O(g(x))\text{ olarsa }x \to a\,

Ancaq və ancaq
: \limsup_{x\to a} \left|\frac{f(x)}{g(x)}\right| .

## Nümunə
Tipik istifadədə, O işarəsinin formal tərifi birbaşa istifadə edilmir; Bunun yerinə, f funksiyası üçün O işarəsi aşağıdakı sadələşdirilmiş qaydalara görə əldə edilir: 
* Əgər f (x) bir neçə terminin cəmidirsə, ən yüksək artım nisbətinə sahib olan termin varsa, bu termin saxlanıla bilər və digər terminlər isə çıxarılır.
* Əgər f (x) bir neçə terminin hasilidirsə, istənilən sabit (x'dən aslı olmayanlar) çıxarıla bilər.

Məsələn, tutaq ki, biz *f*(*x*) = 6*x*4 − 2*x*3 + 5 funksiyasını O işarəsinin köməyi ilə sadələşdirmək istəyirik. Bu funksiya üç həddin cəmidir: 6*x*4, −2*x*3, və 5. Üç həddin biri ən yüksək böyümə sürətinə malik olan 6*x*4 dür. Bu zaman biz ikinci qaydanı tətbiq edə bilərik: 6*x*4 6 və *x*4 ün hasilidir hansı ki, 1-ci vuruq x dən aslı deyil. Bu faktoru nəzərə almamaq *x*4 ün sadələşdirilməsinə təsir edə bilər. Buna görə də biz deyirik ki, *f*(*x*) (*x*4)ün "böyük oh" işarəsidir. Riyazi yolla, biz

***f''(''x'') = ''O''(''x''<sup>4</sup>)'''

yaza bilərik. Bu hesablama formal tərifin istifadəsi ilə təsdiq oluna bilər: ''f''(''x'') = 6''x''<sup>4</sup> − 2''x''<sup>3</sup> + 5 və ''g''(''x'') = ''x''<sup>4</sup>. Yuxarıdakı formal tərifi tətbiq etməklə yaza bilərik ki ''f''(''x'') = ''O''(''x''<sup>4</sup>) özünün genişlənməsi olan
: <math>|f(x)| \le \; M |x^4|</math>
: ''x''<sub>0</sub> və ''M'' `in uyğun qiymətləri üçün və bütün ''x'' &#x3E; ''x''<sub>0</sub> üçün bərabərdir. Bunu isbat etmək üçün ''x''<sub>0</sub> = 1 və ''M'' = 13. O zaman bütün ''x'' &#x3E; ''x''<sub>0</sub>:

: <math>\begin{align}|6x^4 - 2x^3 + 5| &\le 6x^4 + |2x^3| + 5\\
                                      &\le 6x^4 + 2x^4 + 5x^4\\
                                      &= 13x^4\end{align}</math>
beləliklə
: <math> |6x^4 - 2x^3 + 5| \le 13 \,x^4 .</math>

= İstifadəsi =
: Böyük O işarəsinin 2 əsas tətbiq sahəsi var: sonsuz asimptotlar və sonsuz kiçik asimptotlar."Böyük O" nun formal tərifi hər iki vəziyyətdə eyni olub, yalnız funksiya arqumentinin limitləri dəyişməkdədir.

= Sonsuz asimptotlar =
: Böyük O işarəsi, alqoritmlərin səmərəliliyini analiz etmək üçün faydalıdır. Məsələn, n ölçülü məsələni həll etmək üçün lazım olan zaman (addım sayı) ''T''(''n'') = 4''n''<sup>2</sup> − 2''n'' + 2 düsturu ilə tapılır. n böyüdükcə ''n''<sup>2</sup> elə sürətlə böyüyəcək ki, digər həddlərin böyümə sürəti bununla müqayisədə kifayət qədər kiçik olacaqdır. Məsələn ''n'' = 500üçün 4''n''<sup>2</sup> həddi 2''n'' həddindən 1000 dəfə böyükdür. Bundan əlavə, əgər biz eyni ifadəni ''n''<sup>3</sup> və ya ''n''<sup>4</sup> həddləri üçün istifadə etsək vuruqlar öz önəmini itirəcəkdir. ''T''(''n'') = 1,000,000''n''<sup>2</sup>və ''U''(''n'') = ''n''<sup>3</sup> olarsa ikinci ifadə ''n'' 1,000,000`u keçdikdə birinci ifadə ilə müqayisədə hər zaman böyük olacaqdır.
: (''T''(1,000,000) = 1,000,000<sup>3</sup>= ''U''(1,000,000)).
: Bu halda böyük O işarəsi bu ifadəni daha sadə halda təqdim edir:
:: <math>\ T(n)= O(n^2) \, </math> və ya
:: <math>T(n)\in O(n^2) \, </math> və deyə bilərik ki alqoritmin ''n<sup>2</sup>'' dərəcədən zaman mürəkkəbliyi var.

= Sonsuz kiçik asimptotlar =
: Böyük O eyni zamanda riyazi ifadə olan "xəta" nı ifadə etmək üçün də istifadə edilə bilər. Məsələn,
:: <math>\begin{align}
e^x &=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+\dotsb &\text{bütün } x\\
    &=1+x+\frac{x^2}{2}+O(x^3)                             &\text{as } x\to 0\\
    &=1+x+O(x^2)                                           &\text{as } x\to 0\\
\end{align}</math>
:: İkinci ifadə (''O''(''x''<sup>3</sup>) ilə olan) xətanın mütləq qiymətinin ''e''<sup>''x''</sup> − (1 + ''x'' + ''x''<sup>2</sup>/2) 0`a yaxın x qiyməti üçün sabitlə ''x''<sup>3</sup> hasilindən daha kiçik olduğunu göstərir.

= ***Hasil*** =
:: <math> f_1 = O(g_1) \text{ və } f_2 = O(g_2)\, \Rightarrow f_1  f_2 = O(g_1  g_2)\,</math>
:: <math>f\cdot O(g) = O(f g)</math>
:: 

= ***Cəm*** =
:: <math> f_1 = O(g_1) \text{ və }
  f_2= O(g_2)\, \Rightarrow f_1 + f_2 = O(|g_1| + |g_2|)\,</math> Bu o deməkdir ki, <math> f_1 = O(g) \text{ və } f_2 = O(g) \Rightarrow f_1+f_2 \in O(g) </math>, hansı ki <math>O(g)</math> qabarıq konusdur.
:: Əgər f və g müsbət funksiyalar olarsa <math>f + O(g) = O(f + g)</math>

== Ədəbiyyat ==
* İsmayıl Calallı (Sadıqov), "[[İnformatika terminlərinin izahlı lüğəti]]", 2017, "[[Bakı]]" nəşriyyatı, 996 s.

= ***Sabitə vurulması**' =
::: K sabit olarsa
::: \ O(k g) = O(g) əgər k 0dan fərqlidirsə
::: f= O(g) \Rightarrow kf = O(g). 
:::