---
title: 'Asimptotik Gösterim'
source: 'https://academia.sh/tr/kurslar/algoritmalar/asimptotik-gosterim'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:32+00:00'
license: 'CC BY-SA 4.0'
---

# Asimptotik Gösterim

Büyük O, büyük omega ve büyük teta tanımları, sabitlerin elenmesi, toplam ve çarpım kuralları, yaygın yanlış okumalar.

Önceki ders, ölçütü işlem sayısı olarak belirledi ama bir sorun bıraktı: bin elemanlık
bir dizide 1000 mü, 1002 mi karşılaştırma yapıldığı önemsizdir. Bu ayrıntılar
gerçekleştirime bağlıdır; algoritmanın kendisine ait olan, **girdi büyüdükçe işlem
sayısının hangi hızla arttığıdır**.

Asimptotik gösterim, bu hızı yakalayan ve gerisini eleyen dildir.

## Büyük O: Üst Sınır

$f$ ve $g$, pozitif tam sayılardan pozitif gerçel sayılara fonksiyonlar olsun.

$$
f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \in \mathbb{N} : \forall n \geq n_0,\ f(n) \leq c \cdot g(n)
$$

Sözle: **yeterince büyük** her $n$ için $f$, $g$'nin sabit bir katını aşmıyorsa,
$f$ en fazla $g$ kadar hızlı büyür.

Tanımın iki niceleyicisi de gereklidir. Sabit $c$, çarpansal farkları eler — iki katı hızlı
çalışan bir gerçekleştirim aynı sınıfta kalır. Eşik $n_0$ ise küçük girdilerdeki
düzensizlikleri eler; asimptotik ifade, büyük girdiler hakkında bir iddiadır.

Bir örnek üzerinde açıkça gösterilebilir. $f(n) = 3n^2 + 5n + 20$ için $g(n) = n^2$
seçilirse, $c = 4$ ve $n_0 = 8$ değerleri tanımı sağlar:

```python
def f(n: int) -> int:
    return 3 * n**2 + 5 * n + 20

c, n0 = 4, 8
print(f(7) <= c * 7**2)            # False  — eşiğin altında sağlanmıyor
print(f(8) <= c * 8**2)            # True
print(all(f(n) <= c * n**2 for n in range(n0, 10_000)))    # True
```

Yedide sağlanmaması bir sorun değildir: tanım, **eşikten sonrası** için bir şey söyler.
Sekizden itibaren eşitsizlik hep geçerlidir; dolayısıyla $3n^2 + 5n + 20 = O(n^2)$
yazılır.

## Büyük Omega: Alt Sınır

$$
f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \geq n_0,\ f(n) \geq c \cdot g(n)
$$

Büyük O bir tavan, büyük omega bir taban verir. "Bu algoritma en az şu kadar iş yapar"
demek için kullanılır.

Alt sınırlar, tek bir algoritma için değil **problem** için konuşulduğunda güçlüdür:
"karşılaştırmalı sıralama en az $\Omega(n \log n)$ karşılaştırma gerektirir" ifadesi,
hiçbir karşılaştırmalı algoritmanın bu sınırın altına inemeyeceğini söyler. Bu tür bir
sonuç, arama ve sıralama konusunda kanıt fikriyle birlikte ele alınacaktır.

## Büyük Teta: Sıkı Sınır

$$
f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{ ve } \ f(n) = \Omega(g(n))
$$

Teta, büyümenin **tam olarak** $g$ mertebesinde olduğunu söyler: hem tavan hem taban aynı
fonksiyondur.

$3n^2 + 5n + 20$ ifadesi $\Theta(n^2)$'dir. Aynı ifade $O(n^3)$ de olur — üst sınır
gevşek olabilir — ancak $\Theta(n^3)$ değildir.

Günlük kullanımda büyük O, çoğu zaman sıkı sınır kastedilerek yazılır. Bu bir kolaylıktır;
kesin konuşulması gereken yerlerde teta tercih edilir.

## Sadeleştirme Kuralları

Karmaşıklık ifadeleri birkaç kuralla sadeleşir.

**Sabit çarpanlar elenir.** $O(3n) = O(n)$. Sabit, tanımdaki $c$ tarafından zaten
soğurulur.

**Toplamda büyük terim kalır.** $O(n^2 + n) = O(n^2)$. Ardışık iki bölümden pahalı olanı
belirleyicidir.

**Çarpımda çarpanlar korunur.** İç içe döngülerde maliyetler çarpılır:
$O(n) \cdot O(\log n) = O(n \log n)$.

**Geçişlilik geçerlidir.** $f = O(g)$ ve $g = O(h)$ ise $f = O(h)$'dir.

| İfade | Sadeleşmiş | Gerekçe |
|---|---|---|
| $5n + 100$ | $O(n)$ | Sabitler ve sabit terim elenir |
| $n^2 + 1000n$ | $O(n^2)$ | Büyük terim baskın |
| $\log_2 n$ ile $\log_{10} n$ | Aynı $O(\log n)$ | Taban değişimi sabit çarpandır |
| $2^{n+1}$ | $O(2^n)$ | $2^{n+1} = 2 \cdot 2^n$ |
| $n! $ ile $2^n$ | Farklı sınıflar | Faktöriyel üstelden hızlı büyür |

Üçüncü satır sık sorulan bir noktayı yanıtlar: logaritmanın tabanı belirtilmez, çünkü
taban değişimi yalnızca sabit bir çarpan üretir ve o çarpan elenir.

## Sabit ve Eşiği Bulmak

Bir iddiayı kanıtlamak, uygun bir $c$ ve $n_0$ **üretmek** demektir. Polinomlar için
mekanik bir yöntem vardır: her düşük dereceli terim, $n \geq 1$ için baskın terimle
sınırlanır ve katsayılar toplanır.

$f(n) = 3n^2 + 5n + 20$ örneğinde $n \geq 1$ için $5n \leq 5n^2$ ve $20 \leq 20n^2$
yazılabilir. Toplandığında $f(n) \leq 28n^2$ çıkar; yani $c = 28$, $n_0 = 1$ da tanımı
sağlayan geçerli bir çifttir.

Yukarıda $c = 4$ ile daha küçük bir sabit bulundu, ama gerekli değildi: tanım **bir**
çiftin varlığını ister, en küçüğünü değil. Bu, asimptotik iddiaların neden kolay
kanıtlandığını açıklar — kaba bir sınır bile yeterlidir.

## Yaygın Yanlış Okumalar

**"$O(n)$ demek, tam olarak $n$ işlem demek değildir."** Üst sınırdır; $3n$ ve $n/2$
ikisi de $O(n)$'dir.

**"$O$ en kötü durum demek değildir."** İkisi ayrı eksenlerdir. En iyi, en kötü ve
ortalama durumların her biri için ayrı ayrı $O$, $\Omega$ ve $\Theta$ yazılabilir. "En
kötü durumda $O(n^2)$" ile "her durumda $O(n^2)$" farklı iddialardır.

**"Küçük $O$ her zaman daha iyi değildir."** Asimptotik gösterim sabitleri elediği için,
$O(n \log n)$ bir algoritma küçük girdilerde $O(n^2)$ bir algoritmadan yavaş olabilir.
Bu, sıralama kütüphanelerinin küçük parçalara farklı algoritma uygulamasının nedenidir.

**Gösterim bir eşitlik değildir.** $f(n) = O(g(n))$ yazımı yerleşmiştir ama yanıltıcıdır;
doğrusu $f \in O(g)$ biçiminde bir küme üyeliğidir. Bu nedenle eşitlik simetrik değildir:
$O(n) = f(n)$ yazılmaz.

## Girdi Büyüklüğü Nedir

Son bir tanım gerekir: $n$ neyi sayar? Yanıt probleme göre değişir ve belirtilmezse ifade
anlamsızdır.

- Dizi işlemlerinde eleman sayısı.
- Metin algoritmalarında karakter sayısı.
- Çizge algoritmalarında hem düğüm hem kenar sayısı — bu yüzden maliyetler $O(V + E)$
  gibi iki değişkenle yazılır.
- Sayısal algoritmalarda genellikle sayının **bit uzunluğu**; sayının kendisi değil.

Son madde ince bir ayrımdır. Bir sayının asal olup olmadığını sayıya kadar bölerek sınayan
yöntem, girdi olarak sayının değeri alınırsa $O(\sqrt{N})$ görünür; oysa girdi $N$ değil,
onu yazmak için gereken bit sayısıdır. Bit uzunluğu cinsinden aynı yöntem üsteldir. Bu
ayrım, karmaşıklık kuramında sınıflandırmanın temelidir ve **Hesaplama Kuramı** kursunda
ele alınır.

## Özet

- Asimptotik gösterim, sabitleri ve düşük dereceli terimleri eleyerek büyüme hızını tutar.
- Büyük O üst sınır, büyük omega alt sınır, büyük teta sıkı sınır verir.
- Tanımdaki $c$ sabiti çarpansal farkları, $n_0$ eşiği küçük girdileri eler.
- Sadeleştirmede sabitler elenir, toplamda büyük terim kalır, çarpımda çarpanlar korunur;
  logaritmanın tabanı yazılmaz, çünkü taban değişimi sabit çarpandır.
- $O$ ile "en kötü durum" farklı eksenlerdir; küçük asimptotik sınıf, küçük girdilerde
  hızlı olmayı garanti etmez.
- Girdi büyüklüğünün ne sayıldığı açıkça belirtilmelidir.

## Sonraki Adım

Büyük O ve omega, sınırın sıkı olup olmadığını söylemez: $n$ hem $O(n)$ hem $O(n^2)$'dir.
Sonraki ders, sınırın kesinlikle gevşek olduğunu belirten küçük gösterimlerini tanımlayacak
ve bunların hangi ifadeleri mümkün kıldığını gösterecek.