[Matematik] Büyük O Gösterimi – Big-Oh | Matematiksel Bir Gösterim Olup Ä°ÅŸlevlerin – Fonksiyonların Asimptotik Davranışlarını Tarif Etmek İçin Kullanı..

Büyük O Gösterimi – Big-Oh

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) = 4n² – 2n + 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 edilebilecek kadar düşük kalacaktır; örneğin n = 500 için 4n² terimi 2n 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 2n terimleri içeren bir ifade ile kıyaslayacak olursak katsayılar da anlamlarını yitirecektir. T(n) = 1.000.000n² 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

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, :

ifadesi hatanın (yani ex − (1 + x + x2 / 2) farkının) mutlak değer bakımından, sıfıra yeterince yakın x değerleri için bir sabit çarpı x3 değerinden daha küçük olduğunu belirtir.

Kaynak: Kadim Dostlar ™ Forum

Bu içerik 27.01.2012 tarihinde Hale tarafından, Matematik ve Geometri Konu Anlatımları bölümünde paylaşılmıştır ve 1822 kez okunmuştur. Bu içeriğin devamında incelemek isteyebileceğiniz 4 adet mesaj daha bulunmaktadır.

[Matematik] Büyük O Gösterimi - Big-Oh | Matematiksel Bir Gösterim Olup İşlevlerin - Fonksiyonların Asimptotik Davranışlarını Tarif Etmek İçin Kullanılır orjinal içeriğine ulaşmak için tıklayın ...