DEV Community

Vebende Akademi
Vebende Akademi

Posted on

Big-O Nedir?

#algorithms #beginners #computerscience #performance

Bir programın hızlı mı yoksa yavaş mı çalıştığını anlamak için yalnızca saniye cinsinden süreye bakmak yeterli değildir. Bilgisayarınız güçlü olabilir, veri miktarı küçük olabilir veya test ortamı gerçek dünyayı temsil etmeyebilir. İşte bu nedenle yazılım dünyasında algoritmaların performansını ölçmek için Big-O Notasyonu kullanılır.

Big-O, bir algoritmanın veri miktarı arttıkça nasıl davrandığını gösteren matematiksel bir gösterimdir.

Big-O Nedir?

Basit bir ifadeyle:

Veri büyüdüğünde algoritmanın çalışma maliyeti nasıl artıyor?

sorusunun cevabıdır.

Örneğin:

  • 10 kayıt üzerinde çalışan bir algoritma
  • 100 kayıt üzerinde çalışan aynı algoritma
  • 1 milyon kayıt üzerinde çalışan aynı algoritma

Her zaman aynı hızda çalışmayabilir.

Big-O bize bu büyümenin şeklini anlatır.

Neden Önemlidir?

Küçük verilerde her şey hızlı görünür.

Örneğin:

sayilar = [1, 2, 3, 4, 5]

for s in sayilar:
    print(s)
Enter fullscreen mode Exit fullscreen mode

Bu kod çok hızlıdır.

Peki liste:

1.000.000 eleman
Enter fullscreen mode Exit fullscreen mode

olursa?

İşte burada algoritmanın verimliliği önem kazanmaya başlar.

Google, Amazon, Netflix, OpenAI gibi büyük sistemlerde milyarlarca kayıt işlendiği için algoritma seçimi kritik hale gelir.

O(1) - Sabit Zaman

En hızlı algoritma türlerinden biridir.

Veri miktarı ne kadar artarsa artsın işlem sayısı değişmez.

Örnek:

sayilar = [10, 20, 30, 40, 50]

print(sayilar[2])
Enter fullscreen mode Exit fullscreen mode

Burada:

sayilar[2]
Enter fullscreen mode Exit fullscreen mode

her zaman tek bir işlem yapar.

Liste:

  • 5 elemanlı olabilir
  • 500 elemanlı olabilir
  • 5 milyon elemanlı olabilir

Sonuç değişmez.

Grafik olarak:

|
|_____
|
+------------
Enter fullscreen mode Exit fullscreen mode

Neredeyse düz bir çizgidir.

O(n) - Doğrusal Zaman

Veri büyüdükçe işlem sayısı aynı oranda artar.

Örnek:

sayilar = [1, 2, 3, 4, 5]

for s in sayilar:
    print(s)
Enter fullscreen mode Exit fullscreen mode

5 eleman varsa:

5 işlem
Enter fullscreen mode Exit fullscreen mode

100 eleman varsa:

100 işlem
Enter fullscreen mode Exit fullscreen mode

1 milyon eleman varsa:

1 milyon işlem
Enter fullscreen mode Exit fullscreen mode

Grafik:

|
|       /
|     /
|   /
| /
+------------
Enter fullscreen mode Exit fullscreen mode

Düz bir eğim oluşturur.

O(n²) - Kare Zaman

İki iç içe döngü kullanıldığında sıklıkla görülür.

Örnek:

sayilar = [1, 2, 3, 4]

for i in sayilar:
    for j in sayilar:
        print(i, j)
Enter fullscreen mode Exit fullscreen mode

4 eleman:

4 x 4 = 16 işlem
Enter fullscreen mode Exit fullscreen mode

10 eleman:

10 x 10 = 100 işlem
Enter fullscreen mode Exit fullscreen mode

1000 eleman:

1000 x 1000 = 1.000.000 işlem
Enter fullscreen mode Exit fullscreen mode

Veri büyüdükçe maliyet çok hızlı artar.

Grafik:

|
|          /
|       /
|    /
| /
+------------
Enter fullscreen mode Exit fullscreen mode

Dik yükselmeye başlar.

O(log n) - Logaritmik Zaman

Çok verimli algoritmalardır.

Her adımda veri kümesini ikiye bölerler.

Örnek:

Bir sözlükte kelime aramak.

Kelimenin baş harfine bakarsınız:

  • İlk yarıda mı?
  • İkinci yarıda mı?

Her adımda seçeneklerin yarısını elersiniz.

Binary Search Örneği 

def binary_search(liste, hedef):

    sol = 0
    sag = len(liste) - 1

    while sol <= sag:

        orta = (sol + sag) // 2

        if liste[orta] == hedef:
            return orta

        elif liste[orta] < hedef:
            sol = orta + 1

        else:
            sag = orta - 1

    return -1
Enter fullscreen mode Exit fullscreen mode

İşlem Sayıları

Veri Sayısı Maksimum Adım
10 4
100 7
1.000 10
1.000.000 20
1.000.000.000 30

Dikkat edin:

1 milyar elemanda bile yaklaşık 30 adım.

Bu nedenle logaritmik algoritmalar çok değerlidir.

O(n log n)

Çoğu modern sıralama algoritmasının karmaşıklığıdır.

Örneğin:

  • Merge Sort
  • Heap Sort
  • TimSort (Python'un varsayılan sıralama algoritması) 
liste.sort()
Enter fullscreen mode Exit fullscreen mode

arkasında çalışan algoritmalar genellikle bu seviyededir.

O(2ⁿ) - Üstel Karmaşıklık

Tehlikeli bölgeye giriş yapıyoruz.

Her yeni veri miktarı işlem sayısını iki katına çıkarır.

Örnek:

n = 5  → 32 işlem
n = 10 → 1024 işlem
n = 20 → 1 milyon işlem
n = 30 → 1 milyar işlem
Enter fullscreen mode Exit fullscreen mode

Bu tür algoritmalar büyük veri kümelerinde kullanılamaz hale gelir.

O(n!)

En kötü senaryolardan biridir.

Permütasyon problemlerinde görülür.

Örnek:

5! = 120
10! = 3.628.800
20! = 2.432.902.008.176.640.000
Enter fullscreen mode Exit fullscreen mode

İşlem sayısı inanılmaz hızla büyür.

Gerçek Hayattan Örnek

Bir öğrencinin adını bulmak istediğinizi düşünün.

O(1)

Öğrenci numarasını biliyorsunuz.

Doğrudan kayda ulaşıyorsunuz.

Tek işlem
Enter fullscreen mode Exit fullscreen mode

O(n)

Sınıftaki herkese tek tek soruyorsunuz.

Ali misin?
Ayşe misin?
Mehmet misin?
...
Enter fullscreen mode Exit fullscreen mode

En kötü durumda herkese sorarsınız.

O(log n)

Öğrenciler alfabetik sıralı.

Ortadan başlarsınız.

M'den önce mi?
M'den sonra mı?
Enter fullscreen mode Exit fullscreen mode

Her seferinde grubun yarısını elersiniz.

O(n²)

Herkesi herkesle karşılaştırıyorsunuz.

Örneğin:

Kim kiminle arkadaş?
Enter fullscreen mode Exit fullscreen mode

ilişkilerini çıkarıyorsunuz.

Bu durumda karşılaştırma sayısı çok artar.

Big-O'da Sabit Sayılar Neden Önemli Değildir?

Aşağıdaki kod:

for i in range(n):
    print(i)

for i in range(n):
    print(i)
Enter fullscreen mode Exit fullscreen mode

Aslında:

2n
Enter fullscreen mode Exit fullscreen mode

işlem yapar.

Fakat Big-O gösteriminde:

O(2n)
Enter fullscreen mode Exit fullscreen mode

yerine

O(n)
Enter fullscreen mode Exit fullscreen mode

yazılır.

Çünkü veri büyüdükçe büyümeyi belirleyen şey katsayı değil, eğrinin şeklidir.

En Sık Görülen Karmaşıklıklar

Karmaşıklık Performans
O(1) Mükemmel
O(log n) Çok İyi
O(n) İyi
O(n log n) Kabul Edilebilir
O(n²) Yavaşlamaya Başlar
O(2ⁿ) Çok Kötü
O(n!) Felaket

Python Geliştiricileri İçin Kritik Noktalar

Aşağıdaki işlemlerin karmaşıklıklarını bilmek günlük geliştirme sırasında büyük avantaj sağlar.

liste.append(x)
Enter fullscreen mode Exit fullscreen mode 
O(1)
Enter fullscreen mode Exit fullscreen mode 
liste[index]
Enter fullscreen mode Exit fullscreen mode 
O(1)
Enter fullscreen mode Exit fullscreen mode 
x in liste
Enter fullscreen mode Exit fullscreen mode 
O(n)
Enter fullscreen mode Exit fullscreen mode 
x in set
Enter fullscreen mode Exit fullscreen mode 
O(1)
Enter fullscreen mode Exit fullscreen mode 
x in dict
Enter fullscreen mode Exit fullscreen mode 
O(1)
Enter fullscreen mode Exit fullscreen mode 
liste.sort()
Enter fullscreen mode Exit fullscreen mode 
O(n log n)
Enter fullscreen mode Exit fullscreen mode

Sonuç

Big-O, bir algoritmanın saniye cinsinden ne kadar sürdüğünü değil, veri büyüdükçe nasıl ölçeklendiğini gösterir.

Bir yazılımcı için en önemli becerilerden biri yalnızca çalışan kod yazmak değil, aynı zamanda büyüyen veri miktarları karşısında performansını koruyan kod yazabilmektir.

Bu nedenle bir algoritma geliştirirken her zaman şu soruyu sormak gerekir:

"Bu kod 100 kayıt yerine 100 milyon kayıt üzerinde çalışsaydı ne olurdu?"

Big-O notasyonu tam olarak bu sorunun cevabını vermek için geliştirilmiştir.

Top comments (0)