Etiket: NP-complete
Üstel zaman
Üstel zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğunun en fazla <math>e ^ p(n) \,</math> katı tane adımda çözebildiği bir problemdir (p, herhangi bir polinom olabilir). Doğal olarak, üstel zaman polinomsal zamanı içi...
Çokterimli zaman
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.
Sabit zaman
Sabit zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğundan bağımsız olarak n tane adımda çözebildiği bir problemdir. Sabit zaman, polinomsal zamanın bir alt kümesidir.
Polinomsal zamanda çalışan algoritma
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.
Polinomsal zaman
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.
P ile NP arasındaki ilişki
P harfi "polynomial", NP harfleri ise "non-deterministic polynomial" ifadelerini temsil eder, türkçe karşılıkları "polinom" ve "belirleyici olmayan polinom"dur.
Logaritmik zaman
Logaritmik zamanda çalışan bir algoritma, bir Turing makinesinin girişin uzunluğu <math>n \,</math> ise en fazla <math>\log(n) \,</math> civarı adımda çözebildiği bir problemdir. Örneğin, ikili arama algoritması logaritmik zamanda...
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.