Bir Algoritmanın Zaman Karmaşıklığı ve Alan Karmaşıklığı Açıklanıyor
Aynı işi yapan iki programı düşünün. Her birine bin kayıt verin, aralarında hiçbir fark yok. Ama bir milyar kayıt verirseniz, biri Enter tuşunu bırakmadan işi bitirirken diğeri önümüzdeki Salıya kadar çalışmaya devam eder.
Aynı dizüstü bilgisayar. Aynı veriler. Onları ayıran şey zaman karmaşıklığıdır; bu da bir algoritmanın iş yükünün, ona daha fazla girdi verdikçe ne kadar hızlı arttığını ifade eden bir isimden ibarettir.
Terimin gerçekte ne anlama geldiğini, Big O gösteriminin bunu nasıl yazdığını, gerçek bir kod parçasından nasıl hesaplanacağını ve alan karmaşıklığının nerede devreye girdiğini ele alacağız. Son olarak, tüm bunların ödev olmaktan çıkıp gerçek paraya mal olmaya başladığı bir noktaya geleceğiz: akıllı sözleşmeler.
Bir algoritmanın zaman karmaşıklığı nedir?
Saniyeleri bir anlığına unutalım. Zaman karmaşıklığı adımları sayar. Karşılaştırmalar, atamalar, arada sırada yapılan biraz aritmetik işlemler ve toplamı, girdi boyutu olan n'nin bir fonksiyonu olarak yazarsınız.
İşte akla gelebilecek en sıkıcı işlev:
python def print_all(items): for item in items: print(item)
On ürün mü? Döngüden on kez geçmek. On bin ürün mü? On bin kez geçmek.
İşlem, girişin yanında düz bir çizgi halinde yükseliyor, bu yüzden buna O(n) diyoruz.
Şimdi, belki de her yolculuk aslında bir yerine üç küçük işlem gerektiriyor. Tamam, bu 3n. Dürüst olmak gerekirse, kimsenin umurunda değil, çünkü listeyi ikiye katlamak yine de işi ikiye katlıyor ve bu büyüme eğrisi istediğimiz kısım. Tam sayı bilerek göz ardı ediliyor.
Bu yüzden de her Veri Yapıları ve Mimari (DSA) kursu ve kodlama mülakatlarının yarısı zaman karmaşıklığına vurgu yapıyor. Bir algoritmanın karmaşıklığını ona bakarak anlayabiliyorsanız, test etme fırsatı bulamadığınız girdi verileri üzerinde nasıl davranacağını da tahmin edebilirsiniz. Ki bu da üretim ortamında verilerin büyük çoğunluğunu oluşturur.
Algoritmanın Performansını Ölçmek İçin Çalışma Süresinin Neden Kötü Bir Ölçüt Olduğu
Peki neden zamanlayıcıyla çalıştırmayalım ki? Birçok insan bunu yapıyor ve anlıyorum. Ancak sorun şu ki, yürütme süresi algoritmanızın hiçbir ilgisi olmayan bir sürü şeyi de beraberinde getiriyor:
- Donanım. Beş yıllık dizüstü bilgisayarım ve yepyeni bir bulut depolama cihazı, aynı komut dosyası için tamamen farklı sonuçlar verecektir.
- Programlama dili. Aynı döngüyü C ve Python'da yazarsanız, 10 kat veya daha fazla bir fark görebilirsiniz.
- Sistem yükü. Arka planda çalışan bir güncelleme programı devreye giriyor, çöp toplayıcı uyanıyor, önbellek soğuyor. Sonucunuz değişiyor.
- Hangi veriyi ele geçirmiş olursanız olun. Neredeyse sıralanmış verilerde hızlı çalışan bir sıralama algoritması, karıştırılmış verilerde yavaşlayabilir.
Kronometre size tek bir girdiyle tek bir cihazda tek bir ölçüm yapar. Ondan 100 kat daha fazla veri isteyin, hiçbir şey söyleyemez.
Adım sayıları değişmez. Aynı algoritma, aynı girdi ve ister bir sunucuda Rust olsun ister birinin telefonunda JavaScript olsun, aynı sayıda adım elde edersiniz. Bu yüzden zaman karmaşıklığı, bir şeyi kıyaslamadan önce iki çözüm arasında adil bir mücadeledir. Yine de, ne kadar değerli olursa olsun, sonradan kıyaslama yapmanızı tavsiye ederim. Sadece farklı bir soru.
Büyük O ve Diğer Asimptotik Gösterimlerin Açıklaması
Ders kitaplarında buna asimptotik gösterim denir ki bu, göründüğünden daha kötü bir şey. n'nin çok büyük olmasına izin veriyorsunuz ve küçük şeylerle ilgilenmeyi bırakıyorsunuz, böylece sabit çarpanlar ve küçük girdiler ortadan kalkıyor ve sadece büyüme eğrisi kalıyor. Bunlardan bilmeye değer üç tanesi şunlardır:
| Notasyon | Neyi tanımlıyor? | Açık anlam | Örnek |
|---|---|---|---|
| Büyük O, O(f(n)) | Üst sınır | Algoritma f(n)'den daha hızlı büyümez. | Doğrusal arama O(n)'dir. |
| Büyük-Omega, Ω(f(n)) | Alt sınır | Algoritmanın en az f(n) iş yapması gerekiyor. | Herhangi bir karşılaştırmalı sıralama Ω(n log n)'dir. |
| Büyük-Teta, Θ(f(n)) | Sıkıca bağlı | Üst ve alt sınırlar eşleşiyor | Birleştirme sıralaması Θ(n log n)'dir. |
Pratikte, Big O gösterimini yaklaşık %95 oranında duyacaksınız. Bu, bir üst sınır belirler; yani çalışma süresi parantez içindeki orandan daha hızlı artmaz. Gerçek bir işte yaptığım ilk kod incelemesinde, kıdemli bir geliştirici iç içe bir döngünün yanına "O(n²), lütfen düzeltin" yazmıştı ve bununla kastettiği şey, en kötü durum zaman karmaşıklığının karesel olduğu ve listenin çok daha uzun olacağıydı.
Omega ve Theta çoğunlukla algoritma analizi üzerine üniversite derslerinde kullanılır ve sanırım yıllardır iş yerinde ikisini de yazmadım. Büyük O öne çıkıyor çünkü insanların bir toplantıda gerçekten sorduğu soruyu yanıtlıyor: "Trafik üç katına çıkarsa durum ne kadar kötüleşir?"
Bir teknik ayrıntı beni bir süre şaşırttı. Büyük O yalnızca bir tavan değer olduğundan, O(n) fonksiyonu da teknik olarak O(n²)'dir, tıpkı 1,5 metrelik bir kişinin "2,1 metreden kısa" olması gibi. Doğru ama işe yaramaz. Herkes haklı çıkarabileceği en dar sınırı belirtiyor ve ben de aynısını yapacağım.
Örneklerle Birlikte Yaygın Zaman Karmaşıklığı Sınıfları
Gerçek kodda göreceğiniz sınıf sayısı çok fazla değil, belki korkutucu olanları da sayarsak yedi tane. İşte n = 1.000 için her birinin yaklaşık maliyeti:
| Sınıf | İsim | Tipik örnek | n = 1.000'deki işlemler |
|---|---|---|---|
| O(1) | Devamlı | Dizi indeksi, karma tablo araması | 1 |
| O(log n) | Logaritmik | İkili arama | ~10 |
| Açık) | Doğrusal | Bir listeyi taramak | 1.000 |
| O(n log n) | Doğrusal aritmetik | Birleştirme sıralaması, hızlı sıralama (ortalama) | ~10.000 |
| O(n²) | İkinci dereceden | İç içe döngüler, kabarcık sıralama | 1.000.000 |
| O(2ⁿ) | Üstel | Basit özyinelemeli Fibonacci | Evrendeki atomlardan daha fazlası |
| Açık!) | Faktöriyel | Kaba kuvvet kullanan seyyar satış elemanı | Daha da büyük |
O(1): Sabit Zaman
Python sözlüğünüzde on anahtar veya on milyon anahtar olsun, anahtara göre birini çekmenin maliyeti yaklaşık olarak aynıdır ve listeden öğeleri[5] okumanın maliyeti de aynıdır. Bu düzlük, sabit zamanın tüm amacıdır.
O(log n): Logaritmik Zaman
Ben bunları "1 ile 100 arasında bir sayı tahmin et" algoritmaları olarak düşünüyorum; her tahmin, geriye kalanların yarısını eliyor. İkili arama, sıralı bir listede tam olarak bunu yapar:
Python def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
Bir milyar sıralanmış öğeyle yaklaşık 30 karşılaştırma yapılması gerekiyor, oysa tek tek incelemek bir milyarın tamamını alabilir ve bu bana hala komik geliyor.
O(n) ve O(n log n)
Doğrusal bir algoritma, tıpkı bir elektronik tablo sütunundaki en büyük sayıyı gözle arar gibi, her öğeyi sabit sayıda ziyaret eder. O(n log n), iyi bir sıralama algoritmasının çalışma süresidir. Birleştirme sıralaması, listeyi tek tek öğelere ayırır (log n seviyeli bölme) ve ardından birleştirme sırasında her seviye için bir doğrusal geçiş yapar; bu nedenle, veriler sıralı veya karışık olarak gelse de çalışma süresi aynı kalır.
O(n²) ve Daha Kötü
İkinci dereceden kodlarda neredeyse her zaman bir döngünün içinde başka bir döngü bulunur; tıpkı her çifti karşılaştıran bu tekrarlanan kontrol gibi:
Python fonksiyonu: `def has_duplicate(items): for i in range(len(items)): for j in range(i + 1, len(items)): if items[i] == items[j]: return True return False`
Üstel ve faktöriyel büyüme yöntemleri çok daha kötü. Ders kitaplarında yer alan özyinelemeli Fibonacci algoritması aynı alt problemleri tekrar tekrar çözüyor, bu nedenle n'ye eklenen her +1, işi yaklaşık olarak ikiye katlıyor. n = 20'de bunu fark etmezsiniz; n = 60'ta ise akşam yemeği pişirip yiyebilir, bulaşıkları yıkayabilirsiniz, yine de iş bitmeyecektir.
Zaman Karmaşıklığını Adım Adım Nasıl Hesaplayabilirsiniz?
Zaman karmaşıklığını hesaplamak için neredeyse hiçbir zaman resmi bir kanıta ihtiyacınız olmaz. Bu listeyi kafamda gözden geçiriyorum ve gördüğüm kodların çoğunu kapsıyor:
- n'yi tanımlayın. Giriş boyutunun ne olacağına karar verin: bir listenin uzunluğu, bir grafikteki düğüm sayısı, bir sayıdaki basamak sayısı.
- Her satırdaki işi sayın. Basit ifadeler (atama, karşılaştırma, aritmetik) O(1) maliyetindedir.
- Ardışık bloklar ekleyin. Her biri n döngüden oluşan, art arda gelen iki döngü, n + n = 2n sonucunu verir.
- İç içe geçmiş blokları çarpın. n'nin üzerinde bir döngünün içinde n'nin üzerinde başka bir döngü, n × n = n² sonucunu verir.
- Sabitleri atın. 2n, n olur ve 500, 1 olur.
- Sadece baskın terimi saklayın. n² + n ifadesinde, n büyüdükçe n² kısmı diğer kısımları gölgede bırakır.
Hızlıca çözdüm. Sayımınız T(n) = 3n² + 5n + 2 çıkıyor. Bir milyonu ekleyin: 3n² üç trilyon, 5n beş milyon. Yuvarlama hatası. Buna O(n²) diyelim, bitti.
Tek tek geçmek yerine etrafından atlayarak ilerleyen döngüler daha kurnazdır:
Python fonksiyonu: def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
Her geçişte n yarıya iner, bu nedenle bu while döngüsü yaklaşık log₂(n) turdan sonra pes eder. Bu da aslında "zaman karmaşıklığı ne zaman O(log n) olur?" sorusunun tüm cevabıdır. Geriye kalan miktar her adımda sabit bir faktörle küçülüyorsa, o noktadasınız demektir.
Özyineleme, bir araç daha gerektirir: bir yineleme. Birleştirme sıralaması iki yarı boyutlu iş yapar ve ardından birleştirir, bu nedenle T(n) = 2T(n/2) + n olur. Ana teorem, bu şekildeki yinelemeler için bir özet tablodur ve bu örnek için O(n log n) sonucunu verir.
Rekabetçi programlamadan sıkça kullandığım bir kural var: Normal bir makine saniyede yaklaşık 10⁸ basit işlem gerçekleştirir. Çok kaba bir tahmin, ancak göndermeden önce bir çözümün zaman karmaşıklığını kontrol etmek için yeterli. n 10⁵ olduğunda, O(n²) yaklaşık 10¹⁰ işlem demektir, bu nedenle zaman aşımına uğrarsınız. O(n log n) ise 2 milyondan azdır. Sorunsuz çalışır.
En Kötü Durum, En İyi Durum ve Ortalama Durum Analizi
Aynı algoritmaya farklı girdiler verdiğinizde, yapılması gereken iş miktarı büyük ölçüde değişebilir. Doğrusal arama bunu güzel bir şekilde gösteriyor:
- En iyi senaryo: İstediğiniz şey tam ön sırada duruyor. Tek bir karşılaştırma ve elendiniz.
- En kötü senaryo: ya en sonda olur ya da hiç olmaz. Bu, karşılaştırma sayısı açısından bir farktır.
- Ortalama durum: Eğer eşit olasılıkla herhangi bir yerde olabilseydi, ortalama olarak n/2 civarında kontrol yapardınız. Yine de O(n) karmaşıklığında olduğunu unutmayın.
Bir geliştiriciye bir şeyin "karmaşıklığı" hakkında soru sorarsanız, neredeyse her zaman size en kötü durum zaman karmaşıklığını verecektir, çünkü bu sayı, etrafında planlama yapabileceğiniz bir garantidir.
Diyelim ki API'niz en kötü ihtimalle O(n) sürede bir isteği işliyor. Harika, artık en yavaş isteğin nasıl davrandığını biliyorsunuz ve birisi size kasıtlı olarak çöp veri gönderdiğinde de güvendesiniz. İnsanlar kesinlikle bunu yapıyor: eğer bir saldırgan hangi anahtarların karma tablonuzda çakışmaya neden olduğunu anlarsa, bir süre sadece bu anahtarları göreceksiniz.
Kötü senaryonun neredeyse hiç ortaya çıkmadığı durumlarda ortalama duruma bir göz atmaya değer. Hızlı sıralama (Quicksort) burada en iyi örnektir; ortalama O(n log n) karmaşıklığına sahip olsa da, zaten sıralanmış veriler üzerinde rastgele pivotlar seçerseniz O(n²)'ye kadar kayabilir. Standart kütüphaneler bunu rastgele pivotlar kullanarak veya özyineleme şüpheli derecede derine indiğinde farklı bir sıralama algoritmasına geçerek aşar.
Uzay Karmaşıklığı ve Yardımcı Uzay Nedir?
Algoritmanın harcadığı diğer bir maliyet kalemi ise bellektir. Alan karmaşıklığı, girdi boyutu arttıkça ne kadar belleğe ihtiyaç duyulduğunu takip eder ve zamanla aynı Büyük O gösterimiyle yazılır.
Bu belleğin bir kısmı, ne yaparsanız yapın bedelini ödediğiniz giriş verilerinin kendisidir. Aslında kontrol ettiğiniz kısım ise yardımcı alan olarak adlandırılır; yani kodunuzun çalışırken ayırdığı ek şeyler, geçici değişkenler ve yeni diziler gibi, ayrıca kimsenin başına bela olana kadar hatırlamadığı çağrı yığını.
İşte birkaç kısa örnek:
- İki değişkenin yerini değiştirmek, başka hiçbir şeyden bağımsız olarak birkaç yuva gerektirir, bu nedenle O(1) yardımcı alan gerektirir.
- n öğeden oluşan bir listeyi yeni bir listeye kopyalamak size O(n) ek bellek maliyeti getirir.
- n seviye derinliğinde özyinelemeli işlem, yığında n çerçeve bırakır; bu, dizi hiç oluşturulmamış olsa bile O(n) alan gerektirir.
Sonuncusu yüzünden bir stajyer geliştiricinin bir öğleden sonrasını kaybettiğini izledim. Özyinelemeli fonksiyonları hiç bellek kullanmıyormuş gibi görünüyordu, ancak tamamlanmamış her çağrı, daha derinlerdeki çağrıların geri dönmesini bekleyerek yığında bekletiliyordu ve büyük bir girdiyle karşılaştığında her şey yığın taşmasıyla çöktü.
Optimizasyonun büyük bir kısmı, bellek kullanımını zamanla veya tam tersiyle takas etmekten ibarettir. Memoizasyon, önceden hesapladığınız sonuçları önbelleğe alır; bu da basit Fibonacci algoritmasının zaman karmaşıklığını O(2ⁿ)'den O(n)'ye düşürürken, karşılığında O(n) bellek kullanır. Hash tabloları, kovalara yer harcayarak ortalama O(1) arama süresi sağlar. 64 GB RAM'e sahip bir sunucuda bu takas genellikle mantıklıdır, ancak bir mikrodenetleyicide veya akıllı bir sözleşme içinde iki kez düşünmeniz gerekir.
Yaygın Veri Yapılarının Zaman ve Alan Karmaşıklığı
Doğru veri yapısını seçmek, döngünüzün içindeki her şeyi mikro düzeyde ayarlamaktan genellikle daha iyidir. En sık kullanacağınız veri yapıları için ortalama maliyetler şöyledir:
| Veri yapısı | Erişim | Aramak | Sokmak | Silmek | Uzay |
|---|---|---|---|---|---|
| Sıralamak | O(1) | Açık) | Açık) | Açık) | Açık) |
| Bağlı liste | Açık) | Açık) | O(1) | O(1) | Açık) |
| Karma tablo | Yok | O(1) | O(1) | O(1) | Açık) |
| Dengeli ikili arama ağacı | O(log n) | O(log n) | O(log n) | O(log n) | Açık) |
| İkili yığın | min/maks için O(1) | Açık) | O(log n) | O(log n) | Açık) |
İki dipnot. Bağlı liste ekleme ve silme işlemleri, düğümü zaten elinizde tutuyorsanız yalnızca O(1) karmaşıklığındadır. Ve bir karma tablo, çok sayıda anahtar çakıştığında O(n) karmaşıklığına düşebilir.
Sıralama algoritmaları da aynı derecede çeşitlilik gösterir:
| Sıralama algoritması | En iyi | Ortalama | En kötüsü | Yardımcı alan |
|---|---|---|---|---|
| Kabarcık sıralama | Açık) | O(n²) | O(n²) | O(1) |
| Birleştirme sıralaması | O(n log n) | O(n log n) | O(n log n) | Açık) |
| Hızlı sıralama | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Yığın sıralaması | O(n log n) | O(n log n) | O(n log n) | O(1) |
Birleştirme sıralaması tahmin edilebilir ancak ekstra bellek gerektirir. Yığın sıralaması yerinde sıralama yapar ve aynı en kötü durumu korur. Hızlı sıralama, daha kötü tavan değerine rağmen, pratikte genellikle kazanır.
Blok Zinciri ve Akıllı Sözleşmelerde Zaman Karmaşıklığı
İşte işin eğlenceli kısmı burada başlıyor. Kendi sunucunuzda, özensiz bir algoritma CPU'yu boşa harcar ve belki de bir kullanıcıyı rahatsız eder. Ethereum veya herhangi bir EVM zincirinde ise para israfına yol açar. Akıllı sözleşmenin yürüttüğü her işlem kodu, zincirin yerel para birimiyle ödenen gas ücretine mal olur, bu nedenle işlem sayınız birinin faturasında bir satır olarak görünür. Başka bir deyişle, kötü zaman karmaşıklığı bir bedelle birlikte gelir.
Diyelim ki, her token sahibine ödül ödemek için döngü yapan bir sözleşmeniz var. O(n) karmaşıklığında ve her yeni token sahibiyle birlikte gas maliyeti artıyor. Lansman gününde kimse fark etmiyor.
Sonra hissedar listesi büyümeye devam ediyor. Bir gün ödeme, tek bir bloğun sığdırabileceği gaz miktarının üst sınırı olan blok gaz limitinden daha fazla gaz gerektiriyor. Bundan sonra işlem gerçekleşemiyor. "Yavaş" değil, asla başarılı olamıyor ve bu işlevin arkasında bekleyen fonlar esasen bloke oluyor. Denetçiler bu tür sınırsız döngüleri hizmet reddi saldırısı olarak değerlendiriyor ve bu da gayet haklı.
Çözümler, tamamen karmaşık düşünme biçimine dayanıyor:
- İşi, birden fazla işlem üzerinden sabit boyutlu gruplara bölün.
- Bunu tersine çevirin, böylece her kullanıcı kendi ödülünü talep etsin. Her çağrı O(1) zaman karmaşıklığındadır.
- Döngüyü Merkle probu ile değiştirin.
Zincir üzerinde log n'nin neden bu kadar önemli olduğuna dair bir örnek olarak Merkle ispatlarını çok seviyorum. Bir Merkle ağacı, büyük bir veri yığınını tek bir kök hash'e dönüştürür.
Bir girdinin n'lik bir kümeye ait olduğunu kanıtlamak için yaklaşık log₂(n) hash'e ihtiyacınız vardır. Bir milyon girdi için bu yaklaşık 20'dir. Bir milyon değil. Airdroplar buna dayanır ve hafif Bitcoin cüzdanları, tüm bloğu indirmeden bir işlemi onaylamak için aynı yöntemi kullanır.
Zincir dışı işlemlerde de durum aynı. Her gelen blockchain işlemini, açık olan her faturayı tarayarak bir faturayla eşleştiren bir ödeme arka ucu düşünün. Ödeme başına O(n) karmaşıklık söz konusu ve işletme büyüdükçe bu karmaşıklık daha da yavaşlıyor. Faturaları adres veya kimlik numarasına göre anahtarlanmış bir hash haritasına koyarsanız, her eşleşme O(1) karmaşıklığında olur. Ve eğer bu altyapıyı kendiniz kurmak ve yönetmek istemiyorsanız, Plisio gibi bir kripto ödeme ağ geçidi bunu sizin için yapar.
