Büyük O Gösterimi

Kısaca: Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup ...devamı ☟

Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Daha açık şekilde anlatmak gerekirse, bir işlevin büyümesinin asimptotik üst sınırını daha basit başka bir işlev cinsinden tanımlanması demektir. İki temel uygulama alanı vardır: matematik alanında genellikle kırpılmış bir sonsuz serinin kalan terimini karakterize etmek için kullanılır; bilgisayar bilimlerinde ise algoritmaların bilgi işlemsel karmaşıklığının çözümlemesi için kullanılır.

Bu gösterim ilk olarak Alman sayılar kuramcısı Paul Bachmann tarafından 1892 yılında yazdığı ``Analytische Zahlentheorie`` kitabında kullanılmıştır. Gösterim bir başka Alman matematikçi olan Edmund Landau tarafından yaygın kullanıma sokulmuştur, bundan ötürü bazen Landau sembolü olarak da anılır. Büyük O, İngiliz dilindeki "order of" yani bir şeyin derecesi anlamına gelen söz öbeğini hatırlatmak amacı ile kullanılıyordu ve ilk olarak büyük omicron harfi idi; günümüzde büyük O kullanılmakta ve 0 sayısı hiç kullanılmamaktadır.

Kullanım alanları

Bu gösterimin biçimsel olarak yakın ama temelde farklı iki kullanımı vardır: sonsuz asimptotikler ve infinitesimal asimptotikler. Bu ayrım sadece uygulamadadır ancak "büyük O"nun biçimsel tanımı her iki durumda aynı olup işlev argümanının limitleri değişmektedir.

Sonsuz asimptotikler



Büyük O gösterimi algoritma başarım çözümlemesinde faydalıdır. Söz gelimi ``n`` boyundaki bir problemi çözmek için gereken zaman (adım sayısı) ``T``(``n``) = 4``n``² - 2``n`` + 2 olarak bulunabilir.

``n`` büyüdükçe ``n``² terimi o kadar hızlı büyüyecektir ki diğer terimlerin büyüme hızı buna kıyasla ihmal edilebilir kadar düşük kalacaktır; örneğin ``n`` = 500 için 4``n``² terimi 2``n`` teriminin 1000 katı büyüklüğünde olacaktır ve dolayısıyla bu ikinci terimin değeri tüm ifadenin değerini belirlemede çoğu amaç bakımından ihmal edilebilir bir etkiye sahip olacaktır.

Buna ek olarak, aynı ifadeyi n³ veya 2``n`` terimleri içeren bir ifade ile kıyaslayacak olursak katsayılar da anlamlarını yitirecektir. ``T``(``n``) = 1,000,000``n``² ve ``U``(``n``) = ``n``³ olsa bile ikinci ifade, ``n`` 1,000,000`u geçtikçe birinci ifadeye kıyasla daima daha büyük olacaktır (``T``(1,000,000) = 1,000,000³ = ``U``(1,000,000)).

O halde Büyük O gösterimi işin özünü sade biçimde sunmaktadır: şu şekilde yazabilir

T(n)\in O(n^2)


ve algoritmanın ``n2 dereceden`` zaman karmaşıklığına sahip olduğunu söyleyebiliriz.

Sonsuz küçük asimptotikler



Büyük O aynı zamanda bir matematiksel işlev için geliştirilen yaklaşık işlevin hata terimini tarif etmek için de kullanılabilir. Örneğin, :e^x=1+x+x^2/2+\hbox(x^3)\hbox x \to 0 \hbox\hbox ifadesi hatanın (yani e^x - (1 + x + x^2/2) farkının) mutlak değer bakımından, sıfıra yeterince yakın x değerleri için bir sabit çarpı ``x``3 değerinden daha küçük olduğunu belirtir.

Biçimsel tanım

``f``(``x``) ve ``g``(``x``) gerçel sayılar kümesinin bir alt kümesi üzerinde tanımlanmış iki işlev olsun. Bu durumda deriz ki
``f``(``x``), O(``g``(``x``))dir; ``x`` \to ∞
yalnız ve yalnız
öyle ``x``0 ve ``M`` sayıları varsa ki |``f``(``x``)| ≤ ``M`` |``g``(``x``)|; ``x`` > ``x``0 için.


Aynı gösterim ``f`` işlevinin bir ``a`` gerçel sayısı civarındaki davranışını tarif etmek için de kullanılabilir: Deriz ki
``f``(``x``) O(``g``(``x``))dir; ``x`` \to ``a``
yalnız ve yalnız
öyle &delta;>0 ve ``M`` sayıları varsa ki |``f``(``x``)| &le; ``M`` |``g``(``x``)|; |``x`` - ``a``| < &delta; için.


Eğer ``g``(``x``) ``a`` sayısına yeterince yakın ``x`` değerleri için sıfırdan farklı ise yukarıdaki iki tanım limit superior kullanılarak birleştirilebilir:
``f``(``x``) O(``g``(``x``))dir;``x`` \to ``a``
yalnız ve yalnız
\limsup_ \left|\frac\right| < \infty iken.


Matematikte hem &infin; hem de ``a`` civarındaki asimptotikler kullanılır. bilgi işlemsel karmaşıklık kuramında ise sadece &infin;a giden asimptotikler kullanılır. Ayrıca sadece pozitif değerli işlevler ele alındığından mutlak değer de kullanılmadan yazılabilir.

Örnek

Şu çokterimlilere bakalım:

f(x) = 6x^4 -2x^3 +5 \,
g(x) = x^4. \,


``f``(``x``), O(``g``(``x``)) ya da O(``x``4) derecesindedir diyebiliriz. Tanıma göre, tüm ``x``>1 degerleri için ve ``C`` bir sabit iken, |``f(x)``| &#8804; ``C`` |``g(x)``| ifadesi geçerlidir.

İspat:
|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^3 + 5 \, &nbsp; &nbsp; &nbsp; &nbsp; ``x`` > 1 iken
|6x^4 - 2x^3 + 5| \le 6x^4 + 2x^4 + 5x^4 \, &nbsp; &nbsp; çünkü ``x``3 < ``x``4, ve devam eder.
|6x^4 - 2x^3 + 5| \le 13x^4 \,
|6x^4 - 2x^3 + 5| \le 13 \,|x^4 |. \,


Dikkat edilmesi gereken hususlar

Yukarıda bahsi geçen "``f``(``x``) O(``g``(``x``))dir" ifadesi genellikle ``f``(``x``) = O(``g``(``x``)) şeklinde yazılır. Bu, gösterimin bir nebze kötüye kullanılması demektir. Elbette kastettiğimiz iki işlevin birbirine eşit olmaları değildir. O(``g``(``x``)) olma hali simetrik değildir:

\mbox(x)\,=\,\mbox(x^2) fakat \mbox(x^2)\,\ne\,\mbox(x).


Bu yüzden bazı yazarlar küme gösterimini tercih ederler ve ``f`` \in O(``g``) yazarlar, bunu yaparken de O(``g``)yi ``g`` işlevinin altında kalan tüm işlevlerin kümesi olarak düşünürler.

Ayrıca, aşağıdaki gibi bir "eşitlik"

f(x) = h(x) + \mbox(g(x))


"``f``(``x``) ile ``h``(``x``)nin farkı O(``g``(``x``))dir" olarak anlaşılmalıdır.

Sık rastlanan işlev dereceleri

Aşağıda algoritma çözümlemesinde sıkça karşılaşılan işlev derecelerini görebilirsiniz. Tüm bunlar ``n`` sonsuza giderken durumunda belirtilmiştir. Daha yavaş büyüyen işlevler önce listelenmiştir. ``c`` keyfi bir sabit değerdir.

sözde doğrusal veya üst doğrusal
gösterim !! isim
O(1) >| sabit
O(\log^*n) >| tekrarlı logaritmik
O(\log n) >| logaritmik
O( n^c) >| logaritmik çokterimli
o(n) >| alt doğrusal
O(n) >| doğrusal
O(n \log n) >| doğrusal logaritmik (linearitmik),
O(n^2) >| karesel
O(n^c), c > 1 >| çokterimli, bazen "cebirsel" de denir
O(c^n) >| üssel, bazen "geometrik" de denir
O(n!) >| faktöryel, bazen "kombinatoryel" de denir


Pek sık rastlanmasa da, Büyük O gösterimi ile kullanılan çok daha hızlı büyüyen işlevler mevcuttur, mesela A(``n``,``n``) olarak temsil edilen Ackermann işlevinin tek değerli hali. Bunun tam tersi çok yavaş büyüyen işlevler da vardır, ör. Ackermann işlevinin ters işlevi olan ve genellikle &alpha;(``n``) ile gösterilen işlev. Her ne kadar bu işlevler sınırsız olsa da pratik amaçlar için sabit çarpanlar olarak kabul edilirler.

Özellikler

Eğer bir ``f``(``n``) işlevi diğer işlevlerin sonlu toplamı olarak yazılabiliyorsa o zaman bunların içinden en hızlı büyüyeni ``f``(``n``) işlevinin derecesini belirler. Örneğin
f(n) = 10 \log n + 5 (\log n)^3 + 7n + 3n^2 + 6n^3 \in \hbox(n^3)\,\!. note: "\,\!" forces TeX rendering -->


Özel olarak eğer bir işlev ``n`` terimine bağlı birçokterimli tarafından üstten sınırlandırılabiliyorsa o zaman ``n`` değeri ``sonsuz``a gittikçe çokterimlinin ``düşük dereceli`` terimleri ihmal edilebilir.

O(``n````c``) ve O(``c````n``) çok farklıdır. İkincisi çok çok daha hızlı büyür ve ``c`` sabitinin değeri, bu değer 1 sayısından büyük olduğu sürece, bu durumu değiştirmez. ``nnin herhangi bir kuvvetinden daha hızlı büyüyen bir işleve ``yüksek çokterimli`` (superpolynomial) denir. ``c````n`` biçimindeki herhangi bir üssel işlevden daha yavaş büyüyen işleve ise ``altüssel`` denir. Bir algoritmanın zaman karmaşıklığı hem yüksek çokterimli hem de altüssel olabilir, bu tür algoritmalara örnek olarak bilinen en hızlı çarpanlara ayırma algoritmaları verilebilir.

O(log ``n``) tam olarak O(log(``n````c``)) ile aynıdır. Logaritmalar arasındaki fark sadece sabit değerden kaynaklanan farktır (çünkü log(``n````c``)=``c`` log ``n``) ve bundan ötürü büyük O gösteriminde ihmal edilir. Benzer şekilde farklı tabanlara göre yazılmış logaritmalar da denk kabul edilir.

Çarpma



O(f(n)) O(g(n))
= O(f(n)g(n)) \,

Toplama



O(f(n)) + O(g(n)) = O(\max \lbrace f(n),g(n) \rbrace) \,


Bir sabit ile çarpma



O(k g(n)) = O(g(n)) \!\,, ``k``a‰ 0


Bir sabit ile toplama



O(k\ + g(n)) = O(g(n)) g(n) &isin; o(1) olmadığı takdirde ki bu durumda O(1)dir.


Diğer faydalı özellikler aşağıda belirtilmiştir.

İlişkili asimptotik gösterimler: ``O``, ``o``, &Omega;, &omega;, &Theta;, ``&Otilde;``

Büyük O işlevleri kıyaslamak için en sık kullanılan asimptotik gösterimdir ancak genellikle &Theta; yerine geçen resmi olmayan bir gösterim şeklidir (Theta, bk. aşağısı). Burada konuyla ilgili bazı gösterimleri "büyük O" cinsinden tanımlayacağız:

Gösterim Tanım Matematiksel tanım
f(n) \in O(g(n)) asimptotik üst sınır \lim_ \left>\frac\right| < \infty
f(n) \in o(g(n)) asimptotik olarak ihmal edilebilir \lim_ \frac = 0
f(n) \in \Omega(g(n)) asimptotik alt sınır Is this necessary? (iff ``g``(``n``) = O(``f``(``n``))) --> \lim_ \left>\frac\right| > 0
f(n) \in \omega(g(n)) asimptotik baskın Is this necessary? (iff ``g``(``n``) = o(``f``(``n``))) --> \lim_ \frac = 0
f(n) \in \Theta(g(n)) asimptotik keskin sınır Is this necessary? (iff both ``f``(``n``) = O(``g``(``n``)) and ``g``(``n``) = O(``f``(``n``))) --> f\in O(g) and g\in O(f)


``f``(``n``) = o(``g``(``n``)) ilişkisi "``f``(``n``) ``g``(``n``)nin küçük o`sudur" olarak okunur. Sezgisel olarak bunun anlamı şu demektir: ``g``(``n``), ``f``(``n``) işlevinden çok daha hızlı büyür. Biçimsel olarak söylemek gerekirse bu ifadenin anlamı şudur:

``f``(``n``)/``g``(``n``) ifadesinin limiti sıfırdır.

Büyük O gösterimi bir yana, &Theta; ve &Omega; sembolleri ile yapılan gösterim de bilgisayar bilimlerinde çok sık kullanılır. "Küçük o" daha ziyade matematikte kullanılır ve bilgisayar bilimlerinde kullanımı daha nadirdir. Küçük &omega; nadiren kullanılır.

Genelgeçer kullanımda O &Theta; kullanılması gereken yerlerde kullanılır, söz gelimi keskin bir sınır kastetildiğinde. Örneğin birisi "heapsort ortalama durumda O(``n`` log ``n``)dir" diyebilir oysa asıl kastedilen "heapsort ortalama durumda &Theta;(``n`` log ``n``)dir". Her iki ifade de doğru olmakla birlikte ikincisi daha güçlü bir iddiadır.

Bilgisayar bilimlerinde kullanılan bir başka sembol ise &Otilde;dir (``Yumuşak-O`` olarak okunur). ``f``(``n``) = &Otilde;(``g``(``n``)) şeklindeki gösterim ``f``(``n``) = O(``g``(``n``) log``k````g``(``n``)) (bazı ``k`` değerleri için) için kısa yoldur. Temelde logaritmik çarpanları ihmal eden büyük O gösteriminden başka bir şey değildir. Bu gösterim daha çok algoritma başarımında "küçük kusurlar"ı belirlemeye yönelik başarım kestirimlerinde kullanılır (zira log``k````n``, herhangi bir ``k`` sabiti için, daima o(n)`dir).

Büyük O ve küçük o

Aşağıdaki özellikleri bilmek faydalı olabilir:

  • o(``f``) + o(``f``) &isin; o(``f``)
  • o(``f``) o(``g``) &isin; o(``fg``)
  • o(o(``f``)) &isin; o(``f``)
  • o(``f``) &isin; O(``f``) (ve dolayısıyla yukarıdaki özellikler o ve O ile kombinasyonların çoğuna uygulanabilir).


Çoklu değişkenler

Büyük O (ve küçük o ve &Omega;...) birden çok değişken için de kullanılabilir. Örneğin,

f(n,m) = n^2 + m^3 + \hbox(n+m) \mbox n,m\to\infty


ifadesine göre öyle ``C`` ve ``N`` sabitleri vardır ki

\forall n, m>N:f(n,m) \le n^2 + m^3 + (n+m)C.


Çift anlamlılığı engellemek için hangi değişkenin esas kabul edildiği daima belirtilmelidir çünkü

f(n,m) = \hbox(n^m) \mbox n,m\to\infty


ifadesi,

\forall m: f(n,m) = \hbox(n^m) \mbox n\to\infty.


ifadesinden çok farklıdır.

Kaynakça



Kaynaklar

Vikipedi

Bu konuda henüz görüş yok.
Görüş/mesaj gerekli.
Markdown kullanılabilir.

Büyük O Gösterimi
2 hafta önce

Büyük O (Big-Oh) gösterimi matematiksel bir gösterim olup işlevlerin (fonksiyonların) asimptotik davranışlarını tarif etmek için kullanılır. Daha açık...

Büyük O Gösterimi, 1892, Ackermann işlevi, Algoritma, Alman, Donald Knuth, Gerçel sayı, Limit, Matematik, Mutlak değer, Sayılar kuramı
Cebirle gösterim (satranç)
3 yıl önce

notasyondaki gösterimi ise d8=V'dir. Uluslararası Satranç Federasyonu'nun (FIDE) cebirle gösterim için koyduğu kurallar (Ek E'ye bakınız) Cebirle gösterim sayfası...

Cebirle gösterim (satranç), At (satranç), Fil (satranç), Kale (satranç), Piyon (satranç), Satranç, Satranç taşları, Vezir (satranç), Şah (satranç)
Büyük sayılar
2 hafta önce

Aşırı büyük sayıların bazı gösterimleri: Knuth yukarı ok gösterimi / hiperişlemler / tetrasyon içeren Ackermann işlevi Conway dizisi ok gösterimi Steinhaus-Moser...

Bilimsel Gösterim
3 hafta önce

bilimsel gösterim olarak bilinir. Örneğin 5 943 000 sayısının bilimsel gösterimi 5,943× 10 6 {\displaystyle 10^{6}} ve 0,000832 nin bilimsel gösterimi 8,32×...

Bilimsel gösterim, Sayı, Nicelik
Knuth yukarı ok gösterimi
3 yıl önce

Knuth yukarı ok gösterimi, matematikte, çok büyük tam sayıların gösterim yöntemidir. 1976'da Donald Knuth tarafından geliştirildi. Ackermann işlevi ve...

Steinhaus-Moser gösterimi
3 yıl önce

Matematikte Steinhaus–Moser gösterimi, aşırı derecede büyük sayıları ifade etme anlamına gelir. Steinhaus çokgen gösteriminin genişlemesidir. Üçgenin...

Adem Büyük
2 hafta önce

bir performans gösterdi ve gol krallığında 3. oldu. 19 Nisan 2008'de İstanbulspor'u deplasmanda 5-0 yendikleri maçta 4 gol kaydetti. Büyük, Altay'daki performansı...

Yeryüzündeki En Büyük Gösteri
3 yıl önce

Yeryüzündeki En Büyük Gösteri, Britanyalı biyolog Richard Dawkins'in onuncu kitabıdır. 3 Eylül 2009 yılında İngilizce olarak İngiltere'de ve 2010'un Mart...