Algoritma Analizi

1. Algoritma ve Problem Arasındaki Fark Nedir

• Problem cevabını istediğimi sorudur.
• Algoritma problemin adım adım çözümüdür. 

Her algoritmanın time complexity değeri vardır. Problemler ise bir complexity kümesine dahildirler. P, NP PSPACE, EXPTIME complexity kümeleridir. Bu kümelere ait problemler bulunur, algoritmalar değil. P kümesine ait bir problemin - örneğin sıralama problemi - O(1) , O(n) gibi farklı time comlexity değerine sahip algoritmik çözümleri bulunabilir.

2. Complexity Theory
P (Polynomial) problemler bir formül ile çözülebilirler, NP (Non Polynomial) olanlar ise formül ile değil, sezgisel (heuristic) olarak çözülen problemlerdir. NP problemler formüle dökülemese bile verilen yanıtın doğrulanması konusunda çoğunluklar zorluk çıkarmazlar. Şöyle bir tablo herşeyi açıklıyor.

____________________________________________________________
| Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty
___________________________________________________________|           |
| P            |        Yes           |        Yes         |           |
| NP           |        Yes           |     Yes or No *    |           |
| NP-Complete  |        Yes           |      Unknown       |           |
| NP-Hard      |     Yes or No **     |      Unknown ***   |           |
____________________________________________________________           V

Bir problemin P Olması Neden Önemlidir?

P çok maliyetli olsa bile zaman içinde bir çok P probleme daha basit çözümler bulunmuştur. Problemin P olması ileride daha verimli olabileceği anlamına gelir.

NP
Açıklaması şöyle. NP problem illa çözmesi çok zor olan problem anlamına gelmez.

There are many NP problems which are easy to solve. "NP" simply means "easy to verify". It does not mean hard to solve.

What you are probably thinking of is NP-complete problems which is a subset of the NP problems for which we have very, very good evidence to think they are hard.

NP-Complete
NP-Complete yazısına taşıdım.

NP-Hard
NP-Hard yazısına taşıdım.

Big O Nedir?
Bir O Nedir yazısına taşıdım.