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
Foruma hoş geldin 👋, Ziyaretçi
Forum içeriğine ve tüm hizmetlerimize erişim sağlamak için foruma kayıt olmalı ya da giriş yapmalısınız. Foruma üye olmak tamamen ücretsizdir.
Lineer zaman
- Konuyu Başlatan bullvar_katip
- Başlangıç tarihi
- Tagged users Yok
