Big-O asimptotik gösterimi nedir? Bir kod parçasının zaman karmaşıklığı (Time Complexity) adım adım nasıl hesaplanır? O(1), O(log n), O(n), O(n log n) ve O(n^2) arasındaki performans farkları nelerdir?
[Özet Yanıt]
Big-O Notasyonu, girdi boyutu (n) sonsuza giderken bir algoritmanın harcadığı zamanın (adım sayısının) büyüme üst sınırını tanımlar. En hızlıdan en yavaşa sıralama: \mathbf{O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n) < O(n!)}'dir. Karmaşıklık hesaplanırken sabit katsayılar (2n \rightarrow O(n)) ve düşük dereceli terimler (n^2 + 5n \rightarrow O(n^2)) elenir.
1. Temel Big-O Sınıfları ve Örnekleri Tablosu
| Karmaşıklık | Adı | Açıklama ve Tipik Algoritma Örneği |
|---|---|---|
| O(1) | Sabit Zaman | Veri boyutu ne olursa olsun tek işlemde biter. (Dizi indeksine erişim: arr[0], Hash Map araması). |
| O(\log n) | Logaritmik | Her adımda arama uzayı yarıya iner. (Binary Search / İkili Arama). |
| O(n) | Doğrusal (Lineer) | Veri boyutuyla doğru orantılı tek döngü. (Dizide en büyük sayıyı bulma, Lineer Arama). |
| O(n \log n) | Doğrusal Logaritmik | En verimli sıralama algoritmaları. (MergeSort, QuickSort (ortalama)). |
| O(n^2) | Karesel | İç içe geçmiş 2 döngü. (BubbleSort, SelectionSort, InsertionSort). |
| O(2^n) | Üstel | Her adımda işlem ikiye katlanır. (Özyinelemeli / Recursive Fibonacci). |
2. Kod Üzerinden Adım Adım Karmaşıklık Analizi
def ornek_fonksiyon(liste):
n = len(liste)
print(liste[0]) # O(1) sabit işlem
for x in liste: # n defa döner -> O(n)
print(x)
for i in range(n): # İç içe iki döngü -> n * n = O(n^2)
for j in range(n):
toplam = i + j
# Toplam Zaman = 1 + n + n^2
# Big-O Kuralı: En yüksek dereceli terim alınır, sabitler atılır -> O(n^2)
Big-O Asimptotik Gösterimi ve Zaman Karmaşıklığı Analizi
Big-O gösterimi, bir algoritmanın girdi boyutu (n) sonsuza doğru büyürken, algoritmanın çalışma süresinin veya ihtiyaç duyduğu bellek miktarının en kötü senaryoda (worst-case) nasıl bir üst sınır ile ölçeklendiğini gösteren matematiksel bir asimptotik büyüme modelidir. Donanımdan bağımsız olarak algoritmaların saf verimliliğini kıyaslamayı sağlar.
Bir Kod Parçasının Zaman Karmaşıklığı Adım Adım Nasıl Hesaplanır?
Bir algoritmanın zaman karmaşıklığını bulmak için yürütülen işlem sayısı n cinsinden bir fonksiyon olarak modellenir:
- Temel İşlemleri Belirle (O(1)): Değişken atamaları, aritmetik işlemler, karşılaştırmalar ve dizi indeksine erişimler sabit zamanlıdır (c).
- Döngüleri ve Tekrar Sayılarını İncele:
- Tek bir döngü 0’dan n’e kadar birer birer artıyorsa: n adım.
- İç içe döngüler varsa: Döngülerin adım sayıları çarpılır (n \times n = n^2).
- Sayaç ikiye bölünerek veya ikiyle çarpılarak ilerliyorsa: \log_2 n adım.
- Toplam İşlem Fonksiyonunu Yaz: Tüm adımları toplayarak T(n) fonksiyonu oluşturulur (Örn: T(n) = 3n^2 + 5n + 12).
- Sabit Sayıları ve Katsayıları At: n çok büyüdüğünde katsayıların asimptotik etkisi önemsizleşir (3n^2 \to n^2).
- Dominant (Baskın) Terimi Seç: Fonksiyonda n büyüdükçe en hızlı büyüyen terim alınır, diğerleri elenir: O(n^2).
Örnek Analiz
def ornek_fonksiyon(dizi):
toplam = 0 # 1 işlem -> O(1)
n = len(dizi) # 1 işlem -> O(1)
for i in range(n): # n defa döner
for j in range(n): # n defa döner
toplam += dizi[i] # 1 işlem
for k in range(n): # n defa döner
print(dizi[k]) # 1 işlem
return toplam # 1 işlem -> O(1)
- Toplam Adım Sayısı: T(n) = 1 + 1 + (n \times n \times 1) + (n \times 1) + 1 = n^2 + n + 3
- Baskın Terim Kuralı: En yüksek dereceli terim n^2’dir.
- Sonuç: Bu kod parçasının zaman karmaşıklığı O(n^2)'dir.
Karmaşıklık Sınıfları ve Performans Karşılaştırması
Hızlıdan yavaşa doğru temel asimptotik sınıflar:
O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)
| Gösterim | İsim | Açıklama | Tipik Örnek | n = 1024 İken Adım Sayısı |
|---|---|---|---|---|
| O(1) | Sabit (Constant) | Girdi boyutundan tamamen bağımsızdır; işlem anında biter. | Dizi indeksine erişim (dizi[5]), yığına eleman ekleme (push). |
\approx 1 |
| O(\log n) | Logaritmik (Logarithmic) | Her adımda problem boyutu yarıya iner; son derece verimlidir. | İkili Arama (Binary Search), Dengeli Ağaç işlemleri. | \approx 10 |
| O(n) | Doğrusal (Linear) | Çalışma süresi girdi boyutu ile doğru orantılı olarak artar. | Tekli for döngüsü, Doğrusal Arama (Linear Search). |
1.024 |
| O(n \log n) | Doğrusal-Logaritmik (Linearithmic) | Problemi bölüp her seviyede doğrusal işlem yapan algoritmalar. | Hızlı Sıralama (Quick Sort), Birleştirmeli Sıralama (Merge Sort). | \approx 10.240 |
| O(n^2) | Karesel (Quadratic) | İç içe iki döngü içerir; büyük verilerde performans ciddi oranda düşer. | Baloncuk Sıralaması (Bubble Sort), Seçmeli Sıralama (Selection Sort). | \approx 1.048.576 |
Sık Yapılan Hatalar
Hatalı Yaklaşım: T(n) = 4n + 7 bulunan bir fonksiyona O(4n) demek veya her döngü gördüğünde kodu doğrudan O(n^2) ilan etmek.
Doğru Yaklaşım: Asimptotik analizde sabit katsayılar (4) ve sabit terimler (7) ihmal edilir; karmaşıklık doğrudan O(n) olarak ifade edilir. İç içe döngülerde ise içteki döngünün kaç kez çalıştığı değişken sınırlarına göre mutlaka kontrol edilmelidir (örneğin döngü değişkeni her adımda ikiye katlanıyorsa iç döngü O(\log n) olur).
Kendi yazdığın veya merak ettiğin belirli bir kod bloğunun zaman karmaşıklığını birlikte adım adım hesaplamak ister misin?