Lineer zaman

Lineer zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla n katı tane adımda çözebildiği bir problemdir. Lineer zaman, polinomsal zamanın bir alt kümesidir.

Örneğin, iki kelimenin birbirinin tersi olup olmadığını anlama problemi lineer zamanda çözülebilir:

 İlk adımda, Turing makinesi ilk kelimeyi okur ve o kelimeyi temsil eden bir duruma geçer
 İkinci bir geçişte, Turing makinesi diğer kelimeyi tersten okur
 İkinci okuma sonunda, geldiği durumun ilk durumla aynı olup olmadığına bakar

Dolayısıyla, eğer kelimenin uzunluğu  ise, bu problem o kelime için  adımda bitecek ve iki kelimenin birbirinin tersi olup olmadığını söyleyecektir.

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

Kategori:Karmaşıklık teorisi