Zaman karmaşıklığı

Algoritma analizinde yaygın olarak kullanılan fonksiyonların grafikleri, her bir fonksiyon için girdi boyutu n'nin sonucu olarak N işlem sayısını gösterir.

Teorik bilgisayar biliminde, zaman karmaşıklığı bir algoritma çalıştırmak için gereken bilgisayar zamanını tanımlayan hesaplama karmaşıklığıdır. Zaman karmaşıklığı genellikle algoritma tarafından gerçekleştirilen temel işlemlerin sayısı sayılarak ve her bir temel işlemin gerçekleştirilmesinin sabit bir zaman aldığı varsayılarak tahmin edilir. Böylece, algoritma tarafından gerçekleştirilen temel işlemlerin sayısı ile harcanan zamanın bir sabit faktör ile ilişkili olduğu kabul edilir.

Bir algoritmanın çalışma süresi aynı boyuttaki farklı girdiler arasında değişebileceğinden, genellikle belirli bir boyuttaki girdiler için gereken maksimum süre olan "en kötü durum analizi" dikkate alınır. Daha az yaygın olan ve genellikle açıkça belirtilen ortalama durum karmaşıklığı ise belirli bir boyuttaki girdiler için geçen sürenin ortalamasıdır (bu mantıklıdır çünkü belirli bir boyutta yalnızca sonlu sayıda olası girdi vardır). Her iki durumda da, zaman karmaşıklığı genellikle girdinin boyutunun bir fonksiyonu olarak ifade edilir. Bu fonksiyonun tam olarak hesaplanması genellikle zor olduğundan ve küçük girdiler için çalışma süresi genellikle önemli olmadığından, çoğunlukla girdi boyutu arttığında karmaşıklığın davranışına, yani karmaşıklığın asimptotik davranışına odaklanılır. Bu nedenle, zaman karmaşıklığı genellikle büyük O gösterimi kullanılarak ifade edilir, tipik olarak $O(n)$, $O(n\log n)$, $O(n^{\alpha })$, $O(2^{n})$, vb. burada n girdiyi temsil etmek için gereken bitlerin birim cinsinden boyutudur.

Algoritmik karmaşıklıklar, büyük O gösteriminde görünen fonksiyonun türüne göre sınıflandırılır. Örneğin, zaman karmaşıklığı $O(n)$ olan bir algoritma doğrusal zamanlı algoritmadır ve bazı $\alpha >1$ sabitleri için zaman karmaşıklığı $O(n^{\alpha })$ olan bir algoritma polinom zamanlı algoritmadır.