Bir algoritmanın karmaşıklığını nasıl değerlendirilir…

Bir algoritmanın karmaşıklığını değerlendirmek için, giriş verilerinin boyutuna ($n$) bağlı olarak algoritmanın etkinliğini tanımlayan asimptotik analiz kullanılır. Ana adımlar:

Temel işlemlerin tanımlanması: $n$'ye önemli ölçüde bağlı olan işlemler belirlenir (örneğin, karşılaştırmalar, atamalar, aritmetik işlemler).
İşlem sayısının hesaplanması: Temel işlemlerin sayısı $n$'ye bağlı olarak hesaplanır. Bu, kesin bir formül veya bir tahmin olabilir.
Asimptotik sınıfın belirlenmesi: Büyük O ($O$), Omega ($\Omega$) ve Theta ($\Theta$) gösterimleri kullanılarak üst, alt ve kesin asimptotik davranışlar tanımlanır.
- $O(f(n))$: Algoritma, büyük $n$ için $f(n)$ ile çarpılmış bir sabit tarafından aşılmayan bir zamanda çalışır. En kötü durumu tanımlamak için kullanılır.
- $\Omega(f(n))$: Algoritma, büyük $n$ için en az $f(n)$ ile çarpılmış bir sabit tarafından gerçekleştirilen zamanda çalışır. En iyi durumu tanımlamak için kullanılır.
- $\Theta(f(n))$: Algoritma, büyük $n$ için $f(n)$ ile orantılı bir zamanda çalışır. Ortalama durum veya en iyi ve en kötü durumların aynı asimptotik sıralamaya sahip olduğu durumlar için kullanılır.

En yaygın kullanılan gösterim, algoritmanın en kötü durumda ölçeklenebilirliğini anlamak için önemli olan zamanın üst sınırını tanımlayan Büyük O ($O$) gösterimidir.

Sabitlerin ve daha düşük dereceli terimlerin ihmal edilmesi: Asimptotik belirlemede, sabit çarpanlar ve düşük dereceli terimler göz ardı edilir, çünkü büyük $n$ için en büyük katsayılı fonksiyon baskındır. Örneğin, $3n^2 + 5n + 10$ ifadesinin asimptotik gösterimi $O(n^2)$ olur.

Tipik asimptotik sınıflar (küçükten büyüğe sıralı):

$O(1)$: Sabit zaman (çalışma süresi $n$'den bağımsızdır).
$O(\log n)$: Logaritmik zaman (çalışma süresi $n$ ile çok yavaş artar, ikili arama algoritmaları için karakteristiktir).
$O(n)$: Doğrusal zaman (çalışma süresi $n$ ile doğru orantılıdır, basit doğrusal arama için karakteristiktir).
$O(n \log n)$: Doğrusal-logaritmik zaman (Quick Sort veya Merge Sort gibi verimli sıralama algoritmaları için karakteristiktir).
$O(n^2)$: Kare zaman (çalışma süresi $n$'in karesi ile artar, Bubble Sort gibi basit sıralama algoritmaları için karakteristiktir).
$O(n^c)$ (c > 1 için): Polinom zaman.
$O(c^n)$ (c > 1 için): Üssel zaman (çalışma süresi $n$ ile çok hızlı artar, tüm olasılıkların denenmesi gibi durumlar için karakteristiktir).
$O(n!)$: Faktöriyel zaman (en yüksek sınıf, çok hızlı büyür).

Döngüsel yapılar için asimptotik belirleme:

Sıralı kod blokları: Blokların karmaşıklığı toplanır. $O(A+B) = O(\max(A, B))$.
İç içe döngüler: Döngü sayısı çarpılır. $n$ iterasyonlu bir döngü ile başka bir $m$ iterasyonlu döngü, $O(n \times m)$ karmaşıklığa sahiptir. Eğer $m=n$ ise, karmaşıklık $O(n^2)$ olur.
Giriş boyutunun azaltılmasıyla döngüler: Örneğin, her yinelemede 2'ye bölmek, logaritmik karmaşıklığa ($O(\log n)$) yol açar.

Örnek:

Basit dizi taraması:

# Temel işlemlerin sayımı (karşılaştırmalar, atamalar)
# Ana işlem, döngüdeki karşılaştırmadır
def find_max(arr):
    if not arr:
        return None
    max_val = arr[0]  # 1 atama (dış döngü dışında)
    for i in range(1, len(arr)): # Döngü, len(arr) - 1 kez çalışır
        # Döngü içinde:
        # 1 karşılaştırma (if arr[i] > max_val)
        # potansiyel olarak 1 atama (max_val = arr[i])
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

Dizinin boyutu $n = \texttt{len(arr)}$ ise, döngü $n-1$ kez çalışır. Her yinelemede sabit sayıda işlem yapılır. Toplam işlem sayısı $n$ ile orantılıdır. Asimptotik karmaşıklık: $O(n)$.

Örnek: Eklemeli sıralama (Insertion Sort):

# Temel işlemlerin sayımı
# Ana işlemler: karşılaştırmalar ve atamalar/taşıma işlemleri
def insertion_sort(arr):
    # Dış döngü $n-1$ kez çalışır
    for i in range(1, len(arr)):
        key = arr[i] # 1 atama
        j = i - 1 # 1 atama
        # En kötü durumda iç döngü $i$ kez çalışır
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j] # 1 atama (taşıma)
            j -= 1 # 1 çıkarma ve 1 atama
        arr[j + 1] = key # 1 atama

Dış döngü $n-1$ kez çalışır. En kötü durumda (dizi ters sıralı), iç döngü ortalama olarak $i$ kez çalışır. Tüm dış döngü yinelemeleri toplamında, iç döngüdeki işlemler yaklaşık $1 + 2 + ... + (n-1) \approx n^2/2$ olur. Asimptotik karmaşıklık: $O(n^2)$ en kötü ve ortalama durumda, $O(n)$ en iyi durumda (dizi zaten sıralı). Karmaşıklık değerlendirmesinde genellikle en kötü durum dikkate alınır (Büyük $O$).

Bir algoritmanın karmaşıklığını nasıl değerlendirilir veya asimptotunu nasıl belirlenir?