Big O notasyonu, bir algoritmanın girdi boyutu n büyüdükçe temel işlem adımlarının hangi eğilimle arttığını anlatır. Zaman karmaşıklığı hesaplanırken saniyeyi değil, algoritmanın büyüme davranışını inceleriz. Başka bir ifadeyle soru, “Bu kod kaç saniyede çalışır?” değil, “Girdi büyüdüğünde kaç işlem daha gerekir?” sorusudur.
Big O analizinde n, girdinin boyutunu temsil eder. Bu değer bir listedeki eleman sayısı, bir metindeki karakter sayısı veya işlenecek düğüm sayısı olabilir. Algoritmanın yaptığı karşılaştırma, atama ve toplama gibi temel adımlar sayılarak bir işlem büyüme sınıfı belirlenir. Asimptotik bakış ise özellikle n büyüdüğünde hangi terimin baskın hâle geldiğine odaklanır.
Big O Notasyonu Nedir ve Gerçek Çalışma Süresinden Nasıl Ayrılır?
Big O, bir algoritmanın girdisi büyüdükçe işlem yükünün nasıl arttığını ifade eden matematiksel bir gösterimdir. Örneğin bir algoritma listedeki her elemanı bir kez inceliyorsa işlem sayısı liste boyutuyla birlikte yaklaşık doğrusal artar. Her elemanı diğer tüm elemanlarla karşılaştırıyorsa artış daha hızlı olur ve iç içe tekrarlardan kaynaklanan karesel bir yapı ortaya çıkabilir.
Buradaki “işlem adımı”, programın çalıştığı bilgisayarda geçen saniye anlamına gelmez. Analiz sırasında belirli temel işlemler sayılır ve algoritmanın büyüme eğilimi incelenir. Bu nedenle Big O, gerçek çalışma süresini, donanım performansını veya her çalıştırmada aynı sonucu veren bir performans garantisini göstermez. Aynı algoritmanın çalışma süresi kullanılan işlemciye, programlama diline, derleyiciye, belleğe ve girdinin içeriğine göre değişebilir.
Bir algoritma için en iyi durum, ortalama durum veya en kötü durum analizi yapılabilir. En kötü durum, algoritmanın karşılaşabileceği en uzun çalışma yolunu inceler. Örneğin bir arama algoritmasında aranan değer son elemandaysa ya da hiç bulunamıyorsa, tüm listeyi taramak gerekebilir. Bu yazıda özellikle bu en kötü durum yaklaşımı ele alınacaktır. Böylece algoritmanın karşılaşabileceği yüksek işlem yükünü önceden değerlendirmek mümkün olur.
Zaman Karmaşıklığı Nasıl Hesaplanır? Dört Adımlı Yöntem
Bir algoritmanın zaman karmaşıklığını incelerken aşağıdaki dört adımlı karar çerçevesini kullanabilirsin:
- Girdi boyutunu n olarak belirle. Önce algoritmanın neyi işlediğini tanımla. Bir listenin eleman sayısı, işlenecek metnin karakter sayısı veya bir ağdaki düğüm sayısı n olabilir.
- Baskın işlemi seç. Algoritma içinde n büyüdükçe en çok tekrarlanan karşılaştırma, atama veya başka temel işlemi belirle. Karmaşıklığı çoğunlukla bu işlem yönlendirir.
- Döngüleri ve işlem sırasını incele. Art arda çalışan bölümlerin işlem sayıları toplanır. İç içe döngülerde ise bir döngünün her tekrarı diğer döngüyü çalıştırdığı için işlem sayıları çarpılır. Kod karşılaştırmalarında bu fark daha net görülebilir.
- Sabit katsayıları ve düşük dereceli terimleri çıkar. Büyük girdilerde büyümeyi belirleyen baskın terim bırakılır.
3n + 5ifadesinde3sabit katsayı,5ise sabit ek işlemdir. Geriye baskın büyüme olaraknkaldığı için sonuçO(n)olur.n² + 2n + 1ifadesinde isen²terimi baskındır ve sonuçO(n²)olarak yazılır.
Bu sadeleştirme, diğer terimlerin hiç işlem gerektirmediği anlamına gelmez. Ama n büyüdükçe sabitler ve düşük dereceli terimler, baskın terimin oluşturduğu büyüme karşısında daha az belirleyici olur. Örneğin art arda iki bölümün maliyeti n + n = 2n ise karmaşıklık O(n) kabul edilir. İç içe iki bölümün maliyeti n × n = n² ise sonuç O(n²) olur.
O(1), O(log n), O(n), O(n log n) ve O(n²) Nasıl Ayırt Edilir?
Bu karmaşıklık sınıflarını ayırt etmenin temel yolu, girdi boyutu n büyüdüğünde algoritmanın yaptığı işin nasıl arttığına bakmaktır. Big O, belirli bir bilgisayardaki gerçek süreyi değil, işlem adımlarındaki büyüme eğilimini açıklar.
| Karmaşıklık sınıfı | Sezgisel işlem modeli | Kısa örnek | Analiz notu |
|---|---|---|---|
| O(1) | Girdi boyutundan bağımsız sabit iş | Bir dizinin belirli indeksindeki elemana erişmek | Girdi büyüse bile temel işlem sayısı aynı kalır. |
| O(log n) | Her adımda arama alanını küçültmek | Sıralı listede ortadaki elemana bakarak arama yapmak | Her adımda elenen bölüm nedeniyle artış yavaştır. |
| O(n) | Girdiyi bir kez baştan sona taramak | Listedeki her değeri sırayla kontrol etmek | İşlem sayısı, listedeki eleman sayısıyla birlikte artar. |
| O(n log n) | Veriyi bölerek işlemek ve seviyeler boyunca taramak | Parçalara ayrılan veriyi her seviyede birleştirerek işlemek | Bölme adımları ile her seviyedeki toplam işlem birlikte değerlendirilir. |
| O(n²) | Her öğeyi diğer öğelerle karşılaştırmak | Listedeki tüm çiftleri kontrol etmek | Genellikle iki boyutlu karşılaştırma veya iç içe tekrar fikriyle ilişkilidir. |
Bir algoritmayı incelerken yalnızca döngü sayısına bakmak yeterli değildir. Döngünün kaç kez çalıştığı, her turda arama alanının küçülüp küçülmediği ve işlemlerin art arda mı yoksa iç içe mi yürüdüğü birlikte değerlendirilir. Ayrıca sabit katsayılar ve küçük ek işlemler çoğu Big O analizinde baskın büyüme eğiliminin yanında ikinci planda kalır.
Bu ayrımı kod yazma dilinden bağımsız biçimde geliştirmek için dil bağımsız Algoritmik Düşünme Testi üzerindeki sorular, işlem sırasını ve problem çözme yaklaşımını değerlendirmeye yardımcı olabilir.
Liste Arama Örneğinde Big O Analizi
Bir listedeki hedef değeri bulmak için değerleri sırayla kontrol eden basit bir algoritma, doğrusal aramaya örnektir. Hedef bulunduğunda return ile döngü sonlandırılır.
def contains_value(numbers, target):
for number in numbers:
if number == target:
return True
return False
numbers = [4, 9, 13, 21, 35]
print(contains_value(numbers, 4))
print(contains_value(numbers, 18))Beklenen çıktı:
True
Falseİlk aramada hedef değer listenin ilk öğesidir. Algoritma yalnızca bir karşılaştırma yaptıktan sonra durabildiği için bu, en iyi duruma örnektir ve karmaşıklığı O(1) olarak ifade edilir.
Hedef listenin sonunda bulunuyorsa bütün öğeler kontrol edilir. Hedef listede hiç yoksa yine listenin tamamı taranır. Bu nedenle en kötü durumda karmaşıklık O(n) olur. Erken dönüş, bazı aramalarda yapılacak işi azaltır; ancak hedefin sonda olması veya hiç bulunmaması hâlindeki en kötü durum karmaşıklığını değiştirmez.
Benzer örnekleri farklı programlama dilleriyle karşılaştırarak incelemek istersen yazılım bilgisi testleri merkezindeki alıştırmalar kod okuma ve algoritma analizini pekiştirebilir.
Art Arda Çalışan Döngüler ile İç İçe Döngüler Nasıl Karşılaştırılır?
Art arda çalışan iki döngü genellikle işlem sayılarının toplanmasıyla, iç içe çalışan iki döngü ise tekrarların çarpılmasıyla analiz edilir. Bu nedenle iki döngünün kodda peş peşe yazılması tek başına O(n²) anlamına gelmez.
Art arda çalışan iki döngü: O(n) + O(n) = O(n)
Aşağıdaki örnekte aynı liste üzerinde iki ayrı işlem yapılır. İlk döngü toplamı hesaplar, ikinci döngü ise 2'den büyük öğeleri sayar.
sayilar = [1, 2, 3]
toplam = 0
for sayi in sayilar:
toplam += sayi
ikiden_buyuk = 0
for sayi in sayilar:
if sayi > 2:
ikiden_buyuk += 1
print(toplam, ikiden_buyuk)Beklenen çıktı:
6 1İlk döngü listedeki n öğeyi bir kez gezer ve O(n) zaman alır. İkinci döngü de aynı listeyi bir kez gezer ve O(n) zaman alır. İşlemler birbirinin içinde olmadığı için karmaşıklık O(n) + O(n) = O(2n) olur. Sabit katsayı göz ardı edildiğinde sonuç O(n) olarak yazılır.
İç içe çalışan iki döngü: O(n) × O(n) = O(n²)
Bu örnekte dış döngüdeki her öğe için iç döngü listenin tamamını yeniden gezer. Üç öğeli listede her öğe, üç öğeyle eşleştirilir. Kendisiyle yapılan eşleşmeler de sayıldığı için toplam 3 × 3, yani 9 çift oluşur.
sayilar = [10, 20, 30]
cift_sayisi = 0
for ilk in sayilar:
for ikinci in sayilar:
cift_sayisi += 1
print(cift_sayisi)Beklenen çıktı:
9Dış döngü O(n), iç döngü de her dış döngü adımında O(n) kez çalıştığı için toplam karmaşıklık O(n) × O(n) = O(n²) olur.
Döngüleri analiz ederken kullanabileceğin kontrol listesi
- İkinci döngü, ilk döngünün içinde mi?
- İki işlem aynı girdi boyutuyla mı çalışıyor?
- Döngü sınırları her adımda küçülüyor mu?
- İşlemler ayrı ayrı mı tamamlanıyor?
Bu sorular, döngülerin gerçekten nasıl tekrarlandığını görmeyi kolaylaştırır. Her iç içe döngü otomatik olarak O(n²) değildir. İç döngü sabit sayıda çalışabilir, girdinin boyutundan bağımsız olabilir veya her adımda problemin bir bölümünü eleyebilir. Bu nedenle yalnızca döngülerin görünüşüne değil, toplam tekrar sayısına bakmak gerekir.
Sık Sorulan Sorular
Big O Notasyonu gerçek çalışma süresini gösterir mi?
Hayır. Big O, bir algoritmanın girdi boyutu büyüdükçe işlem adımlarının artış eğilimini gösterir. Saniye cinsinden gerçek süreyi, donanım performansını veya kesin bir performans garantisini ifade etmez.
İç içe iki döngü her zaman O(n²) midir?
Hayır. Her iki döngü de girdi boyutuna bağlı olarak n kez çalışıyorsa O(n²) sonucu ortaya çıkar. Ancak iç döngü sabit sayıda çalışabilir, her adımda daha az tekrar yapabilir veya farklı bir artış kuralına sahip olabilir.
O(log n) zaman karmaşıklığı sezgisel olarak ne anlama gelir?
O(log n), her adımda incelenen problemin önemli bir bölümünün elenmesi anlamına gelir. Örneğin kalan arama alanı her adımda yaklaşık yarıya indiriliyorsa, girdi büyüse bile gerekli adım sayısı yavaş artar.
Art arda çalışan iki O(n) işlem neden O(n) kabul edilir?
Çünkü bu işlemler birbirinin içinde değil, peş peşe çalışır. Toplam işlem sayısı O(n) + O(n), yani O(2n) olur. Big O analizinde sabit katsayılar göz ardı edildiği için sonuç O(n) şeklinde yazılır.
Art arda ve iç içe döngüleri ayırmanın temel yolu, işlemlerin kaç kez tekrarlandığını ve birbirlerinin çalışma alanını genişletip genişletmediğini incelemektir.
