İçeriğe atla

Lineer zaman

Vikipedi, özgür ansiklopedi
22.52, 8 Mart 2013 tarihinde Addbot (mesaj | katkılar) tarafından oluşturulmuş 12903099 numaralı sürüm (Bot: Artık Vikiveri tarafından d:q1372395 sayfası üzerinden sağlanan 7 vikilerarası bağlantı taşınıyor)

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