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 هستن .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
همونطور که میدونیم ، ممکنه الگوریتم های مختلفی برای حل یک مسئله وجود داشته باشن . مثلا برای مرتب سازی یک سری داده ، الگوریتم هایی نظیر : Bubble sort-Selection sort و .....وجود دارن . برای تشخیص دامنه ی کارآمدی الگوریتم ها ، به معیار هایی نظیر پیچیدگی زمانی و پیچیدگی فضای حافظه نیاز داریم. بنابراین منظور
ما از تجزیه و تحلیل الگوریتم ها ، مشخص کردن زمان اجرای برنامه ها هست . هر پردازنده در هرلحظه بیش از یک دستور رو نمیتونه اجرا کنه و این مستقل از نوع پردازنده و سیستم هست. پس هر برنامه در کامپیوتر ها باید دستور به دستور انجام بشه و بنابراین تعداد دستورات برنامه ، مدت زمان اجرای برنامه را نشون میدن . هدف از
تعیین تعداد مراحل این است که بتونیم پیچیدگی زمانی دو برنامه روکه عمل مشابهی انجام می دن مقایسه کنیم و بتونیم میزان افزایش زمان اجرا رو در زمان تغییر مشخصات نمونه ، پیشبینی کنیم . الان ، اصطلاحات و نمادهایی رو معرفی می کنیم که ما رو قادر می سازه عبارات با معنی در مورد زمان و فضای پیچیدگی یک برنامه ایجاد کنیم .
ما از تجزیه و تحلیل الگوریتم ها ، مشخص کردن زمان اجرای برنامه ها هست . هر پردازنده در هرلحظه بیش از یک دستور رو نمیتونه اجرا کنه و این مستقل از نوع پردازنده و سیستم هست. پس هر برنامه در کامپیوتر ها باید دستور به دستور انجام بشه و بنابراین تعداد دستورات برنامه ، مدت زمان اجرای برنامه را نشون میدن . هدف از
تعیین تعداد مراحل این است که بتونیم پیچیدگی زمانی دو برنامه روکه عمل مشابهی انجام می دن مقایسه کنیم و بتونیم میزان افزایش زمان اجرا رو در زمان تغییر مشخصات نمونه ، پیشبینی کنیم . الان ، اصطلاحات و نمادهایی رو معرفی می کنیم که ما رو قادر می سازه عبارات با معنی در مورد زمان و فضای پیچیدگی یک برنامه ایجاد کنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
معمولا زمان اجرای یک برنامه رو با Tn نشون میدن .
اما یکی از نماد های مهم نماد اوی بزرگ هست .
تعریف big O: حد بالای زمان اجرای برنامه هست . به معنای دیگر ، زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگه c>0 وجود داشته باشه به طوریکه
fn<=cgn
اما یکی از نماد های مهم نماد اوی بزرگ هست .
تعریف big O: حد بالای زمان اجرای برنامه هست . به معنای دیگر ، زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگه c>0 وجود داشته باشه به طوریکه
fn<=cgn
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
وقتی میگیم On^2 یعنی تمام توابعی که رشدشون کمتر یا مساوی تابع n^2 هست . و وقتی پیچیدگی زمانی یک الگوریتم On^2 باشه یعنی در بدترین حالت ممکن ، تابع پیچیدگی زمانیش از n^2 بیشتر نمیشه ..پس پیچیدگی رو برحسب یک تابع بیان میکنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!)
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
پس مثلا الگوریتمی که مرتبه ی زمانیش در بدترین حالت ممکن برابر با log n باشه ، بسیار از لحاظ زمانی بهتر از الگوریتمی با زمان اجرای n^3 خواهد بود .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
تعریف Ω
حد پایین زمان اجرای یک برنامه هست . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرای Ωgn هست اگه
fn≥Ωgn
حد پایین زمان اجرای یک برنامه هست . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرای Ωgn هست اگه
fn≥Ωgn