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 $n\,$ ise, bu problem o kelime için $2n\,$ adımda bitecek ve iki kelimenin birbirinin tersi olup olmadığını söyleyecektir.

Ayrıca bakınız

• Logaritmik zaman
• Üstel zaman
• NP-complete