***2
مقدمه
qحلهای ارئه شده برای مسائل در حالت کلی غالبا به دو صورت ظاهر می شوند.
1. الگوریتمهایی که پیچیدگی زمانی آنها حداکثر چند جمله ای می باشد.
2. مسائلی که لگوریتمهای ارائه شده برای آنها از درجه نمایی می باشد.
üدسته دوم در عمل کاربرد خاصی ندارند .
qدانشمندان علوم کامپیوتر نشان داده اند که مسئله فروشنده دوره گرد و هزاران مساله دیگر هم ارز هستند .چرا که با داشتن الگوریتمی کار آمد برای یکی از آنها ، برای تمامی آنها الگوریتمی کار آمد خواهیم داشت .
***3
پمسائل رام نشدنی
qمسائلی که نتوان برای آنها الگوریتمی با مرتبه زمانی چند جمله ای پیدا کرد ، مسائل رام نشدنی نامیده می شود .
qالگوریتمهایی با مرتبه زمانی n! , 3n , 2n یا هر الگوریتمی که مرتبه زمانی آن غیر چند جمله ای باشد ( نمایی ) را مسائل رام نشدنی نامند .
***4
مسائلی که الگوریتمهای زمانی چند جمله ای برای آنها پیدا شده است .
مرتب سازی الگوریتم O ( n Log n )
برای جستجو در یک آرایه مرتب ، یک الگوریتم O ( Log n )
برای ضرب ماتریسها یک الگوریتم O ( n 2.38 )
برای ضرب زنجیره ای ماتریسها O ( n3 )
. . .