Bir algoritmanın yavaş olması bazen yalnızca kahvenizin soğuması demektir. Bazen de Güneş’in yakıtını tüketmesi, yıldızların sönmesi ve evrenin soğuk bir karanlığa dönüşmesi demektir. Zaman kompleksitesi tam olarak bu dramatik farkı anlamamızı sağlar: Bilgisayarın ne kadar hızlı olduğundan önce, problemin büyüdükçe nasıl davrandığını sorar. Çünkü bazı problemler vardır ki onları çözmek için daha hızlı işlemci değil, başka bir evren gerekir.
Evrenin yaşı yaklaşık 13,8 milyar yıldır. Bu da kabaca 4,35 × 10^17 saniye eder. İlk bakışta akıl almaz bir süre gibi görünür. Fakat algoritmaların dünyasında bu sayı bazen çocuk harçlığı kadar küçüktür. Özellikle giriş boyutu arttıkça çalışma süresi üstel ya da faktöriyel büyüyen algoritmalar, kozmik takvimle dalga geçer. Onlara bir miktar veri verirsiniz; karşılığında sizden jeolojik çağlar, yıldız ömürleri ve sabır isterler.
Büyüme Hızı: Asıl Canavar
Zaman kompleksitesi, bir algoritmanın çalışma süresini giriş boyutuna göre ifade eder. O(n) doğrusal bir davranıştır: Veri iki katına çıkarsa süre de yaklaşık iki katına çıkar. O(n^2) daha kaprislidir: Veri iki katına çıkarsa süre dört katına çıkar. Fakat O(2^n) ya da O(n!) sahneye çıktığında işler karanlık bir mizaha dönüşür. Çünkü burada artış, merdiven çıkmak değil, roketle uçurumdan düşmek gibidir.
Örneğin gezgin satıcı problemi gibi klasik optimizasyon problemlerinde, tüm olası rotaları denemek isterseniz n şehir için yaklaşık n! farklı olasılıkla karşılaşırsınız. 10 şehir için sorun yönetilebilir görünür. 20 şehirde işler ciddileşir. 50 şehirde ise bilgisayarınızın fanı felsefe yapmaya başlar. 100 şehirde, tüm evreni dev bir süperbilgisayara çevirseniz bile kaba kuvvet yaklaşımıyla kesin çözüm aramak pratik olmaktan çıkar.
Buradaki kritik ders şudur: Donanım hızlanır, ama kötü büyüme hızları daha hızlı hızlanır. İşlemcinizi bin kat güçlendirmek harika görünebilir; fakat üstel karmaşıklık karşısında bu yalnızca birkaç ek giriş boyutu kazanmak anlamına gelir. Yani 2^100 yerine 2^110 seviyesine geldiğinizde zafer kazanmış olmazsınız; sadece uçurumun biraz daha estetik bir noktasından bakarsınız.
Kaba Kuvvetin Sınırı
Kaba kuvvet yöntemi, bütün olasılıkları tek tek denemektir. Basit, dürüst ve çoğu zaman felaket derecede pahalıdır. Bir şifreyi kırmak için tüm kombinasyonları denemek buna örnektir. Eğer olası anahtar sayısı yeterince büyükse, saldırganın problemi matematiksel olarak değil, zamansal olarak duvara çarpar. Modern kriptografinin gücü de kısmen buradan gelir: Çözüm teorik olarak vardır, ama evrenin kullanım kılavuzunda yeterli süre yoktur.
Bu noktada önemli bir ayrım yapmalıyız: Bir problemin çözülebilir olması, pratikte çözülebilir olduğu anlamına gelmez. Matematiksel olarak cevap sonlu sayıda adımda bulunabilir; fakat bu adımların sayısı evrenin yaşını aşıyorsa, pratik dünyada o cevap bir efsaneye dönüşür. Bilgisayar bilimi bu nedenle yalnızca hesaplama sanatı değil, imkânsızlıkları sınıflandırma disiplinidir.
Peki ne yaparız? Pes etmeyiz; zekice hile yaparız. Yaklaşık algoritmalar, sezgisel yöntemler, dinamik programlama, dal-sınır teknikleri, olasılıksal yaklaşımlar ve makine öğrenmesi gibi araçlar tam da burada devreye girer. Amaç her zaman kusursuz cevabı bulmak değildir; çoğu zaman yeterince iyi cevabı yeterince hızlı bulmaktır. Mühendislik, mutlak hakikatin değil, zamanında gelen faydalı cevabın sanatıdır.
Evren Bize Ne Öğretir?
Zaman kompleksitesi, bilgisayar ekranına sıkışmış teknik bir konu değildir. Bize düşünmenin ekonomisini öğretir. Her yolu denemek akıl değildir; doğru soyutlamayı kurmak akıldır. Her problemi güçle ezmeye çalışmak strateji değildir; problemin yapısını görmek stratejidir. Bir savaşçı gibi sorarız: Düşman kim? Cephe nerede? Kaynağım ne kadar? Zaferin tanımı kesin sonuç mu, yoksa yeterince iyi sonuç mu?
Sonuçta bazı algoritmalar evrenden uzun sürer çünkü evren küçük değil, kombinasyonlar canavarcadır. Bu gerçek hem alçakgönüllü hem de özgürleştiricidir. Bize şunu fısıldar: Daha çok hesaplamak her zaman daha iyi düşünmek değildir. Bazen en büyük ilerleme, işlemci hızında değil, soruyu yeniden biçimlendirmede saklıdır. Evren yaşlanırken hâlâ dönen bir algoritma görmek istemiyorsak, kod yazmadan önce büyüme hızının dilini öğrenmeliyiz.