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, Turing makinesi

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 2 n , adımda bitecek ve iki kelimenin birbirinin tersi olup olmadığını söyleyecektir.

Ayrıca bakınız: Polinomsal zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğuna göre en fazla bir polinom tane adımda çözebildiği bir problemdir.

Logaritmik zaman, Logaritmik zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğu n , ise en fazla log(n) , civarı adımda çözebildiği bir problemdir. Örneğin, ikili arama algoritması logaritmik zamanda çalışır.

Üstel zaman, Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla e ^ { p(n) } , katı tane adımda çözebildiği bir problemdir (p, herhangi bir polinom olabilir). Doğal olarak, üstel zaman polinomsal zamanı içine alabilir.

NP-complete


Bu makale, online kullanıcı topluluğu tarafından oluşturulan ve düzenlenen özgür ansiklopedi projesi Wikipedia'nın Türkçe versiyonu Vikipedi'deki Lineer zaman maddesinden kopyalanmıştır. Bu makale, GNU Özgür Belgeleme Lisansı ilkeleri kapsamında özgürce kullanılabilir.