Home / Algoritmalar / Big O (Büyük O) Notasyonu Nedir?

Big O (Büyük O) Notasyonu Nedir?

Algoritma Analizi işleminde kullanılan en önemli kavramlardan biri de Big O notasyonudur. Türkçeye Büyük O olarak çevirdiğimiz bu kavram bir fonksiyonun büyümesini ifade eder.

Basit bir şekilde matematiksel olarak anlatmaya çalışırsak f ve g fonksiyonları reel sayı olursa;

f(x) fonksiyonu c ve k sabit olmak üzere büyük O fonksiyonu O(g(x)) şeklinde tanımlanır.

•|f(x)| ≤ c|g(x)|+k

x > k olmalı…

Matematiksel ifadeler kafanızı karıştırabilir. Gelin örnek üzerinde anlatılım.

f(x) = x^2 + 2x + 1 fonksiyonunun büyüme fonksiyonunun x^2(x kare) olduğunu gösterelim.

 

  • İlk olarak x > 1 için;
  • x^2 + 2x + 1 ≤ x^2 + 2x^2 + x^2
  • x^2 + 2x + 1 ≤ 4x^2
  • C = 4 ve k = 1 için;
  • f(x) ≤ Cx^2 +k , x > k durumunun sağlandığını görürüz.

 

Eğer f(x) için O(x^2) ise aynı zamanda O(x^3) diyebiliriz. Ancak bizim niyetimiz en küçük büyüme fonksiyonunu bulmaktır.

 

Fonksiyonların Büyüme Hızları

Fonksiyonların büyüme hızları küçükten büyüğe aşağıdaki gibi sıralanmaktadır. (n sayısını eleman sayısı olarak düşünebilirsiniz.)

• 1
• log n
• n
• n log n
• n2
• n3
• 2n
• n!

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir