Sabit zaman

Vikipedi, özgür ansiklopedi

Sabit zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğundan bağımsız olarak n tane adımda çözebildiği bir problemdir. Sabit zaman, polinomsal zamanın bir alt kümesidir.

Örneğin, bir kelimenin ilk harfinin "a" olup olmadığını bulma problemi sabit zamanda çözülebilir: algoritma, verilen kelimenin ilk harfini okur ve "a" harfi ile karşılaştırıp DOĞRU veya YANLIŞ cevabını yollar. Örneğin, bu fonksiyonun C ile yazılmış hali şu şekildedir:

 int ilk_harf_a_mi( char* kelime )
 {
     return ( kelime[0] == 'a' );
 }

Ve görebileceğiniz üzere kelime uzunluğundan bağımsız olarak tek bir işlem yapıp sonucu bildirecektir.

Ayrıca bakınız: Logaritmik zaman, Üstel zaman, NP-complete