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