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.

Sabit zaman

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[1] == `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

Kaynaklar

Vikipedi

İlgili konuları ara

Yanıtlar