سلام من یه سوال دارم خودم هر چی فکر کردم منظورسو نفهمیدم ممنون می شم با توضیحات کامل کمکم کنید
اگر orderزمانی یک الگوریتم بری حل یک مسئله مشخص تتای nبلشد و میزان مصرف زمان این الگوریتم برای حل یک نمونه مسئله با سایزk،حدود aباشد مشخص کنید اگر تعداد داده های ورودی راnبرابر کنیم مصرف زمان حدودا چقدر خواهد شد؟
چون مرتبه زمانی خطی هست زمان مسئله ای با اندازه n برابر هم n برابر می شه یعنی na
خیلی ممنون
یعنی چی که خطیه و اگر تتای یک یا n^2یا a^nباشه باز هم همینجوریه؟ ممنون
دوست من این سوال شما به این بر می گرده که اصلا مفهوم مرتبه زمانی رو درک کرده باشی یا نه ؟ فکر می کنم اگه یکم توضیح در این مورد برات بنویسم بدردت بخوره . اصلا اینکه چرا بحث مرتبه زمانی مطرح شده و مرتبه زمانی چی هستش ؟ خوب هممون می دونیم که برای حل یک مسئله خاص میتونه روشها یا به عبارت بهتر الگوریتمهای متفاوتی وجود داشته باشه .برای اینکه متوجه بشیم که کدوم الگوریتم برای مسئله مورد نظر ما بهتر جواب میده بحث ارزیابی کارایی الگوریتمها به میون میاد که برای ارزیابی کارایی دو مسئله مطرح میشه : 1- زمان لازم برای اجرای الگوریتم 2- میزان حافظه لازم برای الگوریتم . مورد دوم که همون میزان حافظه مصرفی هستش تقریبا میشه گفت به خاطر افزایش چشم گیر رسانه های ذخیره سازی زیاد اهمیت نداره . مورد اول هم که زمان لازم برای یک الگوریتم هستش به دو بخش زمان کامپایل و زمان اجرا تقسیم میشه . در اینجا هم ذکر این نکته لازم که زمان کامپایل هم اهمیت چندانی نداره ! چرا : به این خاطر که زمان کامپایل برای هر برنامه یک بار هستش و در نتیجه مهمترین فاکتور برای ارزیابی الگوریتمها زمان اجرای الگوریتم هستش ، یعنی مدت زمانی که در زمان اجزای برنامه طول میکشه که الگورتم پیاده سازی شده بتونه جواب مسئله مورد نظر ما رو بدست بیاره . انواع گوناگونی از مسئله ها در دنیای برنامه نویسی وجود داره که به اقتضای اونها الگوریتمهای متفاوتی هم بوجود اومدن که از اون جمله میشه الگوریتمهای حریصانه ، الگوریتمهای پویا و الگوریتمهای تقسیم و غلبه و... که در درس یا کتابهای طراحی الگوریتم به طور کامل باهاش آشنا میشین . خوب وقتی که ما قصد حل یک مسئله رو داشته باشیم اول باید نوع مسئله رو تشخیص بدیم و الگوریتمی مناسب برای حل اون انتخاب کنیم که مهمترین قسمت در حل یک مسئله همین انتخاب الگوریتم مناسب برای حل هستش . خوب حالا الگوریتم مناسب رو پیداا کردیم ، بعد شروع به حل مسئله می کنیم . خوب برای همه مسلمه که یک مسئله همیشه با داده های یکسانی قرار نیست اجرا بشه و در هر بار اجرا برنامه حجم متفاوتی از داده ها به برنامه داده میشه . ما برای اینکه بتونیم یک پیش بینی کلی از رفتار الگوریم با حجم متفاوتی از داده های ورودی رو به دست بیاریم میام برای اون الگوریتم مرتبه زمانیش رو بدست میاریم که یک فرمول برای ما نتیجه میده که از روی اون فرمول میشه رفتار کلی الگوریتم رو بدست اورد . برای بدست آوردن مرتبه زمانی فاکتوری به نام اندازه مسئله مطرح میشه که به عبارتی همون تعداد داده های ورودی در نظر گرفته میشه و در اغلب مسئله ها زمان اجرای الگوریتم تابعی از اندازه مسئله هستش . که البته در بعضی از مسائل این اندازه مسئله مفهوم دیگری دارد . مثلا وقتی قراره K امین عدد از سری فیبو ناتچی رو پیدا کنیم اندازه مسئله همین k در نظر گرفته میشه و لی وقتی قراره که مثلا یک ارایه رو مرتب کنیم اندازه مسئله تعداد عناصر آرایه در نظر گرفته میشه . اگه بخواهیم در این مورد صحبت کنیم با این زودی ها تموم نمیشه . خلاصه کنم بحث رو به این صورت که : برای بیان مرتبه زمانی یک الگوریتم از نمادهای مختلفی مثل O , o, و تتا و امگا استفاده میشه که هر کدوم تعریف خاص خودش رو داره . O یک حد بالا برای مرتبه زمانی و امگا یک حد پایین و تتا یک حد میانی را برای مرتبه زمانیی الگوریتمها تعریف می کنند . خیلی از مواقع برای بدست آوردن مرتبه زمانیی الگوریتم نمیشه با نگاه به ظاهر اون به رفتار اون پی برد که در این مواقع برای بدست آوردن مرتبه زمانی از یک سری سیگمها و فرمول های ریاضی برای این کار استفاده می کنیم .
در انتها هم چند تا مثال از مرتبه زمانی میارم :
کد:
x=x+1
یا
for(i=12;i < 30;++i)
x++;
در دو مثال بالا مرتبه زمانی O(1) می باشد ، خیلی واضح هستش چون که در این دو مثال اصلا اندازه مسئله تغییر نخواهند کرد .
کد:
for(i=1;i<=n;++i)
x++;
در مثال بالا اگه n رو تعداد دادهای ورودی و در نتیجه اندازه مسئله در نظر بگیریم مرتبه زمانی مسئله O(n) در نظر گرفته میشه ، به عبارت دیگه مرتیبه زمانی خطی در نظر گرفته میشه یعنی زمان اجرای برنامه رابطه مستقیمی با اندازه مسئله داره . یعنی اگه اول n=2 بوده و در بار بعدی n=4 باشد به طور تقریبی می توان گفت که زمان اجرای برنامه هم دو برابر می شود .
کد:
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
x++;
در مثال فوق مرتبه زمانی مسئله O(n^2) در نظر گرفته میشه . یعنی با n برابر کردن اندازه مسئله زمان اجرای الگوریتم n^2 برابر می شود .
و به همین ترتیب مثالهای زیادی رو میشه آورد . البته ناگفته نمونه که تعیین مرتبه زمانی همه الگوریتمها با این راحتی نیستش و بدست آوردن مرتبه زمانی بعضی الگوریتمها واقعا به مهارت ریاضی احتیاج دارن .
خوب دیگه ببخشید ، فکر کنم زیادی صحبت کردم . امیدوارم مفید واقع بشه .