Bir algoritmanın zaman karmaşıklığı, genellikle algoritmanın çalışma süresinin, girdi boyutunun değişimine göre nasıl değiştiğini hesaplayan bir yaklaşım olarak tanımlanır.
Big O notasyonu, bir algoritmanın en kötü durumda ne kadar sürede çalışabileceğini belirlemek için kullanılan bir matematiksel ifadedir. Bu notasyon, algoritmanın zaman karmaşıklığını ifade ederek, girdi boyutuna bağlı olarak işlem süresinin nasıl değişeceğini tahmin eder. Zaman karmaşıklığı hesaplanırken genellikle girdi boyutu n olarak belirlenir ve Big O notasyonu, bu girdi boyutuna göre algoritmanın en kötü durumda ne kadar sürede çalışabileceğini belirler. Büyük O karmaşıklık tablosu, farklı algoritmaların karmaşıklıklarını karşılaştırmak ve görselleştirmek için kullanılır. Bu tablo, algoritmaların performanslarını hızlı bir şekilde karşılaştırmak ve en etkili olanı seçmek için önemlidir.
1 < logn < n < nlogn <... < n!
Theta notasyonu, bir algoritmanın en iyi ve en kötü senaryo çalışma zamanlarını sınırlar.
f(x) ve g(x) adındaki iki fonksiyonun c1.|g(x)|<=|f(x)|<=c2.|g(x)| için birer c1, c2 ve k değerleri bulabilirsek f(x)=Θ(g(x)) yani g(x), f(x)'in Thetasıdır.
Bir algoritmanın en iyi senaryodaki çalışma zamanının alt sınırını ifade eder. Bu notasyon bir algoritmanın çalışma zamanının en iyi durumda ne kadar hızlı olabileceğini ifade eder.
f(x) ve g(x) adındaki iki fonksiyonun |f(x)|>=c.|g(x)| her x>=k için birer k ve c değerleri bulabilirsek f(x)= Ω(g(x)) yani g(x), f(x)'in Omegasıdır.
f(x) ve g(x) adındaki iki fonksiyonun |f(x)|<=c.|g(x)| her x>=k için birer k1 ve k2 ve c değerleri bulabilirsek f(x)=O(g(x)) yani g(x), f(x)'in Big O'sudur.
yukarıdaki ifade için
denir.
yukarıdaki ifade için
c ve k reel sayıları bulunur. Bu sebeple ifadenin doğruluğu ispatlanmış olur.
def gauss_toplam(n):
return (n * (n + 1)) // 2
Verilen kod parçasında işlem doğrudan formül kullanılarak yapıldığı için zaman karmaşıklığı O(1) olur. Aynı işlemin formülsüz yapılması
def toplam(n):
toplam = 0
for i in range(1, n + 1):
toplam += i
return toplam
yukardaki gibi for döngüsü kullanılmasına sebep olur. Döngü içindeki işlemin girdi boyutu kadar çalıştırılması sebebiyle bu kod parçasının karmaşıklığı O(n) olur.
n adet pozitif tam sayının girdi olarak kullanıldığı ve bu girdinin toplamının istendiği bir fonksiyonda Big O notasyonu hesaplanırken en büyük etkiyi yapan terim dikkate alınır.
yukarıdaki eşitsizlikten anlaşılacağı üzere
Big O notasyonunu bulabilmek için bir c,k ikilisi seçilmelidir.
def faktoriyel(n):
if n == 0:
return 1
else:
return n * faktoriyel(n - 1)
Yukarıdaki kod parçasında girdinin n olduğu durumda faktoriyel işlemi yapılabilmesi için rekürsif yaklaşım tercih edildi. Bu yaklaşımda fonksiyonun her bir çağrısı için yapılan işlem sayısı sabit olduğu için ve fonksiyon kendini girdi boyutu kadar çağıracağı için karmaşıklık O(n) olur.
n adet pozitif tam sayının girdi olarak kullanıldığı ve bu girdinin çarpımının istendiği bir fonksiyonda Big O notasyonunu hesaplanırken en büyük etkiyi yapan terim dikkate alınır.
n'nin 1'den büyük olduğu durumlar için c,k ikilisi seçeriz.