asdas

Hemen hemen her yazılımcının karşılaştığı meşhur Big-O (Big O Notation) Nedir, Ne İşe Yarar, Neye Göre Belirlenir?

Big-O Notation ile üniversitede Algoritma Analizi dersinde karşılaşmıştım ilk kez. Big-O kısaca algoritmanızın karmaşıklığını ve performansını ölçmek için kullandığımız matematiksel bir ifadedir. 

Algoritma karşılaştırmasında 2 temel kıstas üzerinden değerlendirme yapılır; 

• Zaman Karmaşıklığı
• Bellek Karmaşıklığı

Zaman karmaşıklığı bir algoritmanın girdi ile çıktı arasında geçen zamanı hesaplarken, diğeri de harcanan bellek alanını hesaplar. Bu hesapları biz yazılımcılar genelde en kötü durum veya senaryoya göre (Worst case) değerlendiririz.

• Constant Time — O(1)
Bir algoritmanın girdi verilerine (n) bağlı olmadığında sabit bir zamana sahip olduğu söylenir. Giriş verilerinin boyutu ne olursa olsun, çalışma süresi her zaman aynı olacaktır.

if a > b:
  return True
else:
  return False

• Logarithmic Time — O(log n)
Bir algoritma, her adımda girdi verilerinin boyutunu azalttığında logaritmik zaman karmaşıklığına sahip olduğu söylenir (giriş verilerinin tüm değerlerine bakması gerekmez).

for index in range(0, len(data), 3):
  print(data[index])

• Linear Time — O(n)
Çalışma süresi giriş verilerinin boyutuyla en fazla doğrusal olarak arttığında, bir algoritmanın doğrusal bir zaman karmaşıklığına sahip olduğu söylenir. Bu, algoritmanın girdi verilerindeki tüm değerleri incelemesi gerektiğinde mümkün olan en iyi zaman karmaşıklığıdır.

for value in data:
  print(value)

• Quasilinear Time — O(n log n)
Girdi verilerindeki her işlemin bir logaritma zaman karmaşıklığına sahip olması durumunda, bir algoritmanın yarı doğrusal bir zaman karmaşıklığına sahip olduğu söylenir. Genellikle sıralama algoritmalarında görülür (e.g. mergesort, timsort, heapsort).

Örneğin: data1'deki (O(n)) her değer için data2'de aynı değeri aramak için binary search (O(log n)) kullanırsak.

for value in data1:
  result.append(binary_search(data2, value))

• Quadratic Time — O(n²)
Girdi verilerindeki her bir değer için doğrusal bir zaman işlemi gerçekleştirmesi gerektiğinde, bir algoritmanın ikinci dereceden bir zaman karmaşıklığına sahip olduğu söylenir.

for x in data:
  for y in data:
    print(x, y)

Bubble sort, O (n²) zaman karmaşıklığının bir örneğidir.

• Exponential Time — O(2^n)
Bir algoritmanın, girdi veri setine yapılan her ekleme ile büyüme iki katına çıktığında, üstel bir zaman karmaşıklığına sahip olduğu söylenir. Bu tür zaman karmaşıklığı genellikle brute-force algoritmalarında görülür.

O(2^n) bir örneği, Fibonacci sayılarının özyinelemeli hesaplanmasıdır:

def fibonacci(n):
  if n <= 1:
    return n
  return fibonacci(n-1) + fibonacci(n-2)

• Factorial — O(n!)
Bir algoritma, girdi verilerinin boyutuna bağlı olarak faktöriyel bir şekilde büyüdüğünde, faktöriyel zaman karmaşıklığına sahip olduğu söylenir.

O(n!) sahip bir algoritmanın bir örneği, n nesnenin tüm olası permütasyonlarını oluşturmak için kullanılan heap algoritmasıdır.