Lineer zamanda çalışan bir algoritma bir Turing makinesinin girişin uzunluğunun en fazla n katı tane adımda çöz

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

wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar

Lineer zamanda calisan bir algoritma bir Turing makinesinin girisin uzunlugunun en fazla n kati tane adimda cozebildigi bir problemdir Lineer zaman polinomsal zamanin bir alt kumesidir Ornegin iki kelimenin birbirinin tersi olup olmadigini anlama problemi lineer zamanda cozulebilir Ilk adimda Turing makinesi ilk kelimeyi okur ve o kelimeyi temsil eden bir duruma gecer Ikinci bir geciste Turing makinesi diger kelimeyi tersten okur Ikinci okuma sonunda geldigi durumun ilk durumla ayni olup olmadigina bakar Dolayisiyla eger kelimenin uzunlugu n displaystyle n ise bu problem o kelime icin 2n displaystyle 2n adimda bitecek ve iki kelimenin birbirinin tersi olup olmadigini soyleyecektir Ayrica bakinizLogaritmik zaman Ustel zaman NP complete

Yayın tarihi: Temmuz 13, 2024, 19:18 pm

Üst