Zaman karmaşıklığı

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     vb. burada  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ığı  olan bir algoritma doğrusal zamanlı algoritmadır ve bazı  sabitleri için zaman karmaşıklığı  olan bir algoritma polinom zamanlı algoritma''dır.

 Kaynakça 

Kategori:Bilgisayar bilimi
Kategori:Teorik bilgisayar bilimi