Hesaplama karmaşıklığı

Bilgisayar Biliminde Kavramlar

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Karmaşıklık sınıfları

Karmaşıklık Sınıfları

Tüm problem karmaşıklığı uzayını gösteren bir animasyon

Problem uzayı P’yi gösteren bir görsel

Karmaşıklık Sınıfı -->	P (Polinom Zaman)
Anlamı	Hızlı ve verimli çözülebilir
Örnek	Bir listeyi sıralama
Benzetme	"Belgeleri alfabetik dosyalama"
Ana Nokta	Hesaplama açısından "kolay"dır

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Problem uzayı P ve NP’yi gösteren bir görsel

Karmaşıklık Sınıfı -->	NP (Belirsiz Polinom Zaman)
Anlamı	Çözüm doğrulanabilir; yeni çözüm bulmak zor
Örnek	Sudoku çözümünün doğru olduğunu doğrulama
Benzetme	"Eksik bilgilerle belirli bir belgeyi bulma"
Ana Nokta	Doğrulama "kolay", yeni çözüm bulma zordur

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

P, NP ve NP-Tam problem uzayını gösteren bir görsel

Karmaşıklık Sınıfı -->	NP-Tam
Anlamı	NP içindeki en zorlar. Özeldir; tüm NP’yi çözer
Örnek	Gezgin satıcı problemi
Benzetme	"Zor bir yapbozu çözmek: doğrulaması kolay, çözmesi zor"
Ana Nokta	Bilinen verimli bir çözüm yoktur; bulunursa tüm NP çözülür

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

P, NP, NP-Tam ve NP-Zor problem uzayını gösteren bir görsel

Karmaşıklık Sınıfı -->	NP-Zor
Anlamı	NP-Tam kadar zor ya da daha zor
Örnek	Karmaşık bağımlılıklarla en iyi zamanlama; doğrulanamaz
Benzetme	"Çok kısıtlı, hızlı doğrulanamayan en iyi toplantı saatini belirleme"
Ana Nokta	Pratikte çözmesi mümkün olmayabilir

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

P=NP mi? sorusunu soran bir diyagram

Bilgisayar Biliminde Kavramlar