Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اجازه بدید یک خلاصه از مباحث جلسه ی قبل رو خدمت شما عرض کنم . در جلسه ی گذشته با یکسری از تعاریف اولیه ی مرتبط با الگوریتم و فلوچارت آشنا شدیم و همچنین ویژگی های الگوریتم رو بیان کردیم . کمی هم درباره ی کارآمدی الگوریتم مطالبی ارائه کردیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما در این جلسه به طور کلی میخوایم درباره ی کارآمدی الگوریتم صحبت کنیم . همونطور که گفته شد ، ملاک و معیار کارایی یک الگوریتم ، پیچیدگی زمانی و پیچیدگی فضاست . ما دراین سری از آموزش ها بیشتر درباره ی پیچیدگی زمانی صحبت میکنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما اجازه بدید کمی راجع به پیچیدگی فضا صحبت کنیم تا بعد مفصل بریم سراغ پیچیدگی زمانی
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
شبه کد زیر رو در نظر بگیرید :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
float OP1(float a , float b , float c){
return a+b+c*a/a+c+2.0 ;
}
return a+b+c*a/a+c+2.0 ;
}
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
این برنامه یک عبارت خاصی رو محاسبه میکنه و نتیجه رو برمیگردونه. فضای مورد نیاز برای یک چنین برنامه ای شامل دو بخش ثابت و متغیر است . بخش ثابت ، مستقل از بعضی ویژگی های ورودی و خروجی هست و شامل فضای دستور العمل ، فضای لازم برای ذخیره ی کد برنامه ، فضای لازم برای متغیر های ساختاری با اندازه ی ثابت و ثابت ها و غیره هست . بخش متغیر هم شامل فضای لازم برای متغیر های ساختاری و تغییر پذیر برنامه هست که وابسته به نمونه ی موجود در مسئله هستن . همچنین این بخش شامل فضای لازم برای متغیر های مرجع و پشته ی بازگشتی هم هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
فضای لازم برای هر برنامه ای مثل P رو اگر S(P) فرض کنیم ، میشه به صورت S(P)=c+sp نوشت که توی اون c یک مقدار ثابت هست و sp مشخصات نمونه ی مسئله هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
برای برنامه ای که بالا گفتیم ، نمونه ی مسئله با حروفی نشون داده شدن (a,b,c). با این فرض که همه ی این مقادیر در یک کلمه از حافظه ذخیره بشن متوجه میشیم فضای مورد نیاز برای تابع درون مسئله ، مستقل از ویژگی های نمونه هست . پس sp برابر صفر هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما بریم سراغ پیچیدگی زمانی .
پیچیدگی زمانی یعنی مقدار زمانی که یک کامپیوتر برای اجرای کامل یک برنامه لازم داره . هر برنامه یکسری مراحلی داره و از دستوراتی تشکیل شده . معمولا برای تشخیص زمان اجرای برنامه هم به مراحل اجرای برنامه توجه می کنند . اما یک مرحله از برنامه رو میشه به عنوان یک قسمت بامعنی از نظر دستوری تعریف کرد که زمان اجرای اون به ویژگی های نمونه بستگی نداره . تعداد مراحلی که به هر کدوم از دستورات برنامه باید نسبت داده بشه ، به ماهیت اون دستور بستگی داره .
پیچیدگی زمانی یعنی مقدار زمانی که یک کامپیوتر برای اجرای کامل یک برنامه لازم داره . هر برنامه یکسری مراحلی داره و از دستوراتی تشکیل شده . معمولا برای تشخیص زمان اجرای برنامه هم به مراحل اجرای برنامه توجه می کنند . اما یک مرحله از برنامه رو میشه به عنوان یک قسمت بامعنی از نظر دستوری تعریف کرد که زمان اجرای اون به ویژگی های نمونه بستگی نداره . تعداد مراحلی که به هر کدوم از دستورات برنامه باید نسبت داده بشه ، به ماهیت اون دستور بستگی داره .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
حالا برای آشنایی بیشتر میایم تعداد مراحل لازم برای اجرای برخی از دستورات موجود در یک زبان استاندارد ، مثلا ++C ، رو بررسی میکنیم . البته تعداد مراحل ذکر شده برای برخی دستورات به صورت تقریبی هستن و ممکنه توی برنامه های مختلف تغییر کنن ولی اغلب اوقات به همین شکل هستن .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
📝تمامی توضیحات در این زبان دارای صفر مرحله هست . یعنی برای توضیحات هیچ مرحله ای درنظر گرفته نمیشه .
----------------
📝 دستور های تعریفی و اعلان هم مرحله ای ندارن ( دارای صفر مرحله هستن .) منظور از دستور های تعریفی ، دستوراتی هستند که متغیر ها، ثابت ها ، توابع یا نوع دسترسی رو مشخص میکنن
----------------
📝 هر عبارت دارای 1 مرحله هست . ( به جز عبارات فراخوانی توابع )
----------------
📝 تعداد مراحل عمل انتساب <a>=<b> برابر با تعداد مراحل <b> هست . که a شامل یک متغیر و b شامل یک عبارت هست . البته اگه aتابعی از ویژگی های نمونه باشه ، اونوقت تعداد مراحل انتساب برابر با مجموع اندازه ی متغیر و تعداد مراحل عبارت هست .
----------------
📝 دستور های تعریفی و اعلان هم مرحله ای ندارن ( دارای صفر مرحله هستن .) منظور از دستور های تعریفی ، دستوراتی هستند که متغیر ها، ثابت ها ، توابع یا نوع دسترسی رو مشخص میکنن
----------------
📝 هر عبارت دارای 1 مرحله هست . ( به جز عبارات فراخوانی توابع )
----------------
📝 تعداد مراحل عمل انتساب <a>=<b> برابر با تعداد مراحل <b> هست . که a شامل یک متغیر و b شامل یک عبارت هست . البته اگه aتابعی از ویژگی های نمونه باشه ، اونوقت تعداد مراحل انتساب برابر با مجموع اندازه ی متغیر و تعداد مراحل عبارت هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
📝دستور شرطی if else هم 1 مرحله داره .
..................................
📝حلقه ی for(a;b;c) هم دارای b+c مرحله هست . (منظور از b و c ، تعداد مراحل اونهاست . )
...................................
📝فراخوانی توابع و دستورات مدیریت حافظه دارای 1 مرحله هستن .
..................................
📝حلقه ی for(a;b;c) هم دارای b+c مرحله هست . (منظور از b و c ، تعداد مراحل اونهاست . )
...................................
📝فراخوانی توابع و دستورات مدیریت حافظه دارای 1 مرحله هستن .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
شبه کد زیر رو در نظر بگیرید :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
float sum1(float *a , const int n)
1. {
2. float s=0 ;
3. for ( int i=0;i<n;i++)
4. s=s+a[i];
5, return s;
6. }
1. {
2. float s=0 ;
3. for ( int i=0;i<n;i++)
4. s=s+a[i];
5, return s;
6. }
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
☝️ این شبه کد ، مجموع عناصر درون یک آرایه ی n عضوی رو برمیگردونه.
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
خط اول این برنامه ، مرحله ای نداره
خط دوم دارای 1 مرحله هست
خط سوم که یک حلقه ی تکرار هست ، دارای n+1 مرحله هست .
خط چهارم هم n مرحله داره . (اگرچه عمل انتساب هست ولی n بار داره تکرار میشه . )
خط پنجم دارای 1 مرحله هست .
خط ششم هم مرحله ای نداره .
خط دوم دارای 1 مرحله هست
خط سوم که یک حلقه ی تکرار هست ، دارای n+1 مرحله هست .
خط چهارم هم n مرحله داره . (اگرچه عمل انتساب هست ولی n بار داره تکرار میشه . )
خط پنجم دارای 1 مرحله هست .
خط ششم هم مرحله ای نداره .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
پس میشه گفت تعداد کل مراحل شبه کد بالا برابر با 2n+3 هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
یک سوال :
❓فرض کنیم که تعداد مراحل برنامه ی A برابر 2n+3 و تعداد مراحل برنامه ی B برابر 2n+2 باشد. آیا از این
مطلب میشه نتیجه گرفت که برنامه ی A از B کندتر انجام میشه؟
❓فرض کنیم که تعداد مراحل برنامه ی A برابر 2n+3 و تعداد مراحل برنامه ی B برابر 2n+2 باشد. آیا از این
مطلب میشه نتیجه گرفت که برنامه ی A از B کندتر انجام میشه؟
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
جواب منفیه !!
نمیشه نتیجه ی مشخصی گرفت .. چون مراحل دارای واحد زمانی معینی نیستن . ممکنه 3 مرحله ی موجود برنامه ی A به طور مجموع سریع تر از 2 مرحله ی B باشن .
نمیشه نتیجه ی مشخصی گرفت .. چون مراحل دارای واحد زمانی معینی نیستن . ممکنه 3 مرحله ی موجود برنامه ی A به طور مجموع سریع تر از 2 مرحله ی B باشن .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
پس میشه نتیجه گرفت اون اعداد ثابت ملاک خوبی نیستن پس در پیچیدگی زمانی اونها رو میتونیم درنظر نگیریم و به طور کلی بگیم پیچیدگی زمانی به n وابسته هست . به همین دلیل اصطلاحا میگیم هردو برنامه ی A و B از مرتبه ی n هستن .