سلام
برای اکثرا الگوریتم ها بهترین حالت و یا حالت بدترین و میانگین متاثر از جایگشت ورودی انها ست.مثال بارز الگوریتم های مرتب سازی هستند که برحسب اینکه ترتیب ورودی چگونه است حالت های مختلف الگوریتم شکل میگیردمثلا ممکن است یک ترتیب ورودی برای یک روش مرتب سازی بهترین حالت را شکل دهد در حالی که همین ترتیب برای روش مرتب سازی دیگر بدترین حالت را شکل دهد.
پس برای اینکه الگوریتمی را طوری تغییر بدهیم تا زمان اجرای خوبی در بهترین حالت داشته باشد کافیه ترتیب ورودی را بررسی کنیم که ایا همان حالت خاصی است که برای ان الگوریتم بهترین را تولید میکند یا نه.برای مثال اکثر الگوریتم های مرتب سازی معمول را میتوان طوری تغییر داد تا بهترین زمان اجرای ان[tex]O(n)[/tex] باشد به این صورت که ورودی را یک بار پیمایش کن اگر مرتب باشد انگاه الگوریتم مرتب سازی رو اجرا نکن وگرنه طبق معمول لیست را مطابق با ان الگوریتم مرتب کن.یاداوری میشود که در روش های مرتب سازی معمولا بدون توجه به ساختار ورودی روال مرتب سازی اجرا می شود مثلا اگر مرتب سازی سریع را روی لیست مرتب شده اعمال کنیم بدترین حالت شکل میگیرد در حالی که در الگوریتم اصلاح شده یک بار لیست پیمایش میشود و چون مرتب است اصلا روال مرتب سازی سریع اجرا نمی شود ودر این حالت بهترین حالت شکل میگیرد.
ولی ایا هر الگوریتمی را میتوان به این شکل تغییر داد تا بهترین حالت خوبی داشته باشد.مثلا در مثال بالا که در باره مرتب سازی بود روال مرتب سازی در الگوریتم اصلاح شده برای شکل دهی بهترین حالت اجرا نمی شود ولی همیشه اینطور نیست و گاها در الگوریتم های باید الگوریتم حتما اجرا شود مثل الگوریتم های زمانبدی در سیستم عامل و ممکن است هزینه بررسی ورودی خیلی هم کمتر از زمان اجرای روال ها نباشد یا اصلا تمام ورودی ها در دسترس نباشد تا یک حالت خاصی که برای ان روال بهترین حالت را شکل میدهد بررسی باشد.پس بهتر است به جای بیان اینکه هر الگوریتم را میتوان طوری تغییر داد تا بهترین زمان اجرای خوبی داشته باشد از این جمله که تقریبا هر الگوریتمی را میتوان طوری تغییر داد تا در بهترین حالت زمان اجرای خوبی داشته باشد.استفاده شود.