Zaman Karmaşıklığı Problemleri

1

Merhaba arkadaşlar forum üzerinde bir arkadaşın açtığı bir konu üzerinden gözlemlediğim kadarı ile kimsenin zaman karmaşıklığı konusuna yeterince değinmediğini farkettim. O yüzden bu yazıyı hazırladım. Keyifli olkumalar

Zaman Karmaşıklığı Problemleri

Polynomial, Exponential ve Faktoriyel Büyüme

Algoritmalarda performans yalnızca doğru çalışmakla değil, girdi boyutu arttığında ne kadar sürdüğüyle değerlendirilir. Big-O notasyonu, bu performans artışını ifade eder ve doğru algoritma seçimi için kritik öneme sahiptir.

Bu yazıda üç temel zaman karmaşıklığı türünü inceleyeceğiz:

Karmaşıklık Problem Türü
O(n²) Polynomial
O(2ⁿ) Exponential
O(n!) Katastrofik

1. O(n²) — Polynomial Zaman Karmaşıklığı

Bu karmaşıklık türü, girdi boyutu arttıkça çalışma süresinin polinomsal şekilde yükseldiği algoritmaları ifade eder. Genellikle iç içe döngülerin kullanıldığı yapılandırmalarda görülür. Performans düşer fakat çoğu gerçek dünya problemi için hâlâ kabul edilebilir seviyede ölçeklenebilir olduğu için uygulanabilirliği yüksektir.

Örnekler:

  • Bubble Sort
  • 2D tablo tarama
  • İç içe döngüler
n n²
10 100
50 2500
100 10.000

Orta düzey veri işlemlerinde uygulanabilir.
Daha büyük veri setlerinde O(n log n) algoritmalar tercih edilmelidir.

π (pi) sayısının milyarlarca basamağı Chudnovsky algoritması ile hesaplanmıştır.
Modern büyük sayılarda bu algoritma yaklaşık olarak: O(n · log²n) zaman karmaşıklığına sahiptir. Ve bu yüzeden güçlü bir polynomial algoritma örneği olarak Chudnovsky formülü gösterilebilir.

\frac{1}{\pi} = 12 \cdot \sum_{k = 0}^{\infty} \left( \frac{(-1)^k \cdot (6k)!}{(3k)! \cdot (k!)^3} \cdot \frac{13591409 + 545140134 \cdot k}{640320^{3k + \frac{3}{2}}} \right)

Chudnovsky formulun zaman karmasıklığı O(n · log²n) olarak ifade edilebildiğinden π rekorları hesaplanabilirken,
aynı büyüklükte exponential veya factorial bir problem fiziksel olarak bile çözülemez. kabul edilir.

2. O(2ⁿ) — Exponential Zaman Karmaşıklığı

Exponentially artan karmaşıklıkta, her girdi artışı çalışma süresini katlanarak büyütür. Birkaç eklemeyle bile işlem sayısı hızla kontrolden çıkar. Bu sınıftaki algoritmalar yalnızca çok küçük veri setlerinde uygulanabilir olup, büyüyen problemlerde hesaplaması pratikte mümkün değildir.

Örnekler:

  • Naive recursive Fibonacci
  • Brute-force karar mekanizmaları
n 2ⁿ
10 1.024
20 1.048.576
30 1.073.741.824 :collision:

n değeri biraz arttığında bile işlem sayısı patlayıcı şekilde yükselir.

Exponential zaman karmaşıklığına verilebilecek güzel ve somut örneklerden biri de,
n elemanlı bir kümenin tüm alt kümelerini (power set) üretmek sorunudur.

Örneğin elimizde şu küme olsun:

S = {a, b, c}

Üstteki kümenin alt kümeleri:

{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}

Toplam 8 alt küme var; bu da 2³’e eşit. Genel durumda:

  • n elemanlı bir küme için,

  • her eleman “içinde var mı / yok mu?” şeklinde 2 seçenek sunar,

  • bu yüzden toplam alt küme sayısı 2ⁿ olur.

Dolayısıyla, tüm alt kümeleri üreten basit bir algoritma:

  • Her alt kümeyi tek tek üretip listelediği için,

  • O(2ⁿ) zaman karmaşıklığına sahiptir.

Küçük n değerlerinde bu sorun değilken, n büyüdükçe tablo hızla kontrolden çıkar:

n Alt küme sayısı (2ⁿ)
10 1.024
20 1.048.576
30 1.073.741.824 :collision:

Burada çıkan sonuç gösteriyor ki, exponential algoritmalar küçük veri için makul görünse bile, n büyüdükçe çoğu zaman pratikte kullanılamaz hale geliyor.

3. O(n!) — Katastrofik Zaman Karmaşıklığı

Katastrofik zaman karmaşıklığı türünde ise işlem sayısı girdi boyutu arttıkça gerçeküstü hızda patlar. n değerinin yalnızca biraz yükselmesi bile işlem sayısının fiziksel sınırları aşmasına neden olur. Bu seviyedeki algoritmalar çoğu zaman yalnızca teorik olarak incelenir, çünkü pratikte değil, fiziksel olarak bile çözülebilir olmaktan çıkar.

Örnekler:

  • Traveling Salesman Problem (TSP) brute-force
  • Tüm permütasyonların denenmesi
n n! Yaklaşık Değer
5 120 –
10 3.6 milyon Hesaplanabilir
15 1.3 trilyon Çok zor
20 2.4 × 10¹⁸ (2.4 kentilyon) Uygulanamaz
50 3 × 10⁶⁴ Evrendeki tüm kum tanelerinden çok fazla
60 8 × 10⁸¹ Gözlemlenebilir evrendeki toplam atom sayısından bile büyük!

Dikkat ettiyseniz bu noktadan sonra insan algısı devre dışı kalıyor

Birçok kişi “katrilyon”, “kentilyon” gibi terimleri sadece “çok fazla” olarak algılar. Ancak büyüklüğünü gerçekten kavrayabilmek için şu karşılaştırmaya bakalım:

Gözlemlenebilir evrendeki toplam atom sayısı ≈ 10⁸⁰
60! ≈ 8 × 10⁸¹ > 10⁸⁰

Yani yalnızca 60 eleman için brute-force kombinasyon denemesi yapmaya kalksak,
evrendeki tüm atomlar kadar işlem kapasitesine sahip olsak bile yeterli olmazdı!

Daha gercekçi örnek üzerinden hesaplamak gerekirse

Dünyadaki tüm su molekülleri birer kuantum bilgisayarı olsaydı ne olurdu?

  • Dünya’daki toplam su molekülü ≈ 4.7 × 10⁴⁶
  • Hepsi saniyede 1 işlem yapabilse
  • Çözülmesi gereken işlem sayısı 60! ≈ 8 × 10⁸¹

Hesaplama süresi:

60! çözüm süresi ≈ (8 × 10⁸¹) / (4.7 × 10⁴⁶) ≈ 1.7 × 10³⁵ saniye
≈ 5.4 × 10²⁷ yıl

Yani bu problemi çözmek için dünyadaki her su molekülünü ışık hızında çalışan bir kuantum bilgisayarına çevirsek bile evrenin yaşından 390 trilyon kat daha uzun sürerdi.

Genel Değerlendirme

Zaman Karmaşıklığı Durum Kullanılabilirlik
O(n²) Polynomial :+1: Küçük/orta ölçek
O(2ⁿ) Exponential :warning: Sadece çok küçük n
O(n!) Katastrofik :prohibited: Fiziksel olarak bile imkânsız

Sonuç

Yazı boyunca bir algoritmanın sadece doğru sonuç vermesinin yeterli olmadığını, girdi boyutu büyüdüğünde nasıl davrandığının en az doğru kadar önemli olduğunu göstermeye çalıştım.

Polynomial karmaşıklığa sahip yöntemlerin, belirli sınırlara kadar ölçeklenebilir olduğunu; exponential yaklaşımların küçük veri setlerinde işe yarasa da hızla kontrol dışına çıktığını; faktoriyel yöntemlerin ise yalnızca teoride var olup pratikte mümkün olmadığını, fiziksel olarak bile çözülemez hale geldiğini gerçek dünya analojileri ve günümüzde kullanılan bazı algoritmalar üzerinden anlatmaya çalıştım.

Umarım yazıyı okumaktan keyif almışsınızdır.

5 Beğeni