آموزش ساختمان داده قسمت دوم

سعید ضیادید 1395/1/23 1344

آموزش ساختمان داده  قسمت دوم

سلام عرض میکنم خدمت همه ی شما دوستان

ضیادید هستم و با جلسه ی دوم از آموزش ساختمان داده ها در خدمت شما خواهم بود

در جلسه ی گذشته با تعاریفی اولیه از ساختار داده ای و همچنین الگوریتم آشنا شدیم و گفتیم که برای تعیین میزان کارایی و کارآمدی یک الگوریتم بهتر هست که معیار هایی از جمله پیچیدگی زمانی رو در نظر بگیریم و این پیچیدگی زمانی معمولا به صورت یک تابع بیان میشه .انشاءالله در این جلسه قصد داریم درباره ی پیچیدگی زمانی الگوریتم ها صحبت کنیم .

ببینید دوستان ، هر برنامه در کامپیوتر باید به صورت دستور به دستور انجام بشه . پس میشه تا حدی این رو گفت که تعداد دستورات برنامه مدت زمان اجرای یک برنامه رو نشون میده . اما همه ی دستورات دارای مدت زمان یکسانی نیستن . مثلا دستور ضرب ، مدت زمان بیشتری برای اجرا شدن نیاز داره نسبت به عملی مثل جمع. اما در بحث پیچیدگی زمانی ، ما به آهنگ رشد زمان اجرای الگوریتم نسبت به نمونه ی مسئله (مثل ورودی n) توجه میکنیم  و از این تفاوت های دستوری صرف نظر خواهیم کرد .

در این جا میخوایم واحد های زمانی رو برای تعدادی از دستور های زبان برنامه نویسی ++C بررسی کنیم :

 

سوال : فرض کنید که تعداد مراحل برنامه ی A برابر 2n+3 و تعداد مراحل برنامه ی B برابر 2n+2 باشه . آیا از این مطلب میشه

نتیجه گرفت که برنامه ی A از B کندتر انجام میشه؟

پاسخ : نه ، چون هر مرحله دارای واحد زمانی معینی نیست . ممکنه هر مرحله از برنامه ی B از هر مرحله ی برنامه ی A زمان

بیشتری بگیرد . بنابراین ممکنه برنامه ی B از A کندتر باشد.

این مطلب نشون میده صرفا چند تا دستور نمیتونن به شکل مطلوب سرعت اجرای برنامه هارو نشون بدن و چند تا برنامه رو از نظر سرعت با هم مقایسه ی درست بکنن . پس ما بهتره به تابعی بر حسب ورودی های برنامه (مثلا n) توجه کنیم و به جای بررسی تمام دستور های یک برنامه ، به بررسی آهنگ رشد توابع پیچیدگی زمانی الگوریتم برناممون بپردازیم .

اما برای اینکه بتونیم راحت تر درباره ی پیچیدگی زمانی الگوریتم ها صحبت کنیم و اطلاعات خوبی به دست بیاریم ، باید یکسری نماد هایی رو در بحث پیچیدگی زمانی الگوریتم ها بدونیم .

هرکدوم از این نماد ها ، دارای یک تعریف ریاضی و مفهوم هستن .

نمادهایی که میخوایم معرفی کنیم عبارت هستن از O,o,θ,Ω,ω

معمولا زمان اجرای یک برنامه رو با Tn نشون میدن .

تعریف  big O: حد بالای زمان اجرای برنامه هست . یعنی زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگه c>0  وجود داشته باشه به طوریکه

fn<=cgn

وقتی میگیم On^3 یعنی تمام توابعی که رشدشون کمتر یا مساوی تابع n^3 هست . و وقتی پیچیدگی زمانی یک الگوریتم On^3 باشه یعنی در بدترین حالت ممکن ، تابع پیچیدگی زمانیش از n^3 بیشتر نمیشه .

 

تصویر بالا داره به صورت یک نمودار سرعت رشد برخی از توابع مهم رو نشون میده و ملاکش هم نماد O هست . مثلا از این نمودار میتونیم متوجه بشیم که سرعت رشد تابع n log n از تابع n^2 کمتر هست .

تعریف Ω

حد پایین زمان اجرای یک برنامه هست  . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرای Ωgn هست اگه

fn≥Ωgn

پس Ωgn شامل توابعی هست که رشدشون بزرگتر یا مساوی gn باشه. الگوریتمی با چنین مرتبه ای در بهترین حالت دارای پیچیدگی زمانی gn میشه

.تعریف θ

نماد θ دقیقا مرتبه ی یک الگوریتم رو تعیین میکنه . درواقع θ بیانگر حد متوسط زمان اجرای یک الگوریتم هست یعنی زمان اجرای یک الگوریتم در حالت میانگین .

پس ( θ(g(n) شامل توابعی هست که رشدشون تقریبا مساوی و یکسان با gn  باشه .

اما دوتا نماد دیگر هم داریم که ω و o  هستند . ω شکل اکید و o هم شکل اکید O هست .

این ها نماد هایی بودن که ما در پیچیدگی زمانی از اونها استفاده می کنیم .  الان میخوایم ببینیم که چطور میشه سرعت رشد دو تابع رو باهم مقایسه کرد . یکی از روش های معمول برای این کار استفاده از حد هست .

فرض کنید که ما دو تابع  f و g داریم و میخوایم بدونیم رشد کدوم بیشتره و یا میخوایم بدونیم از چه نمادی باید استفاده کنیم برای این دو تابع . اگه بخوایم از حد استفاده کنیم کافیه عبارت زیر رو حساب کنیم :

lim fx/gx

که x  به سمت بی نهایت میل میکنه .  ( f و g توابعی بر حسب متغیر x هستن)

پس داریم حد در بی نهایت رو محاسبه میکنیم . برای جواب این حد ، 3 حالت داریم :

1-جواب بی نهایت

2-جواب 0

3-جواب یک عدد ثابت غیر از صفر

اگه جواب بی نهایت بشه ، یعنی سرعت رشد تابع f بسیار بیشتر از تابع  g هست . اگه جواب صفر بشه ، یعنی سرعت رشد تابع f بسیار کمتر از تابع  g هست چون اگر متغیر رو به سمت بی نهایت ببریم ، مقدار صورت کسر نسبت به مخرج کسر بسیار کوچک تر میشه .البته هردوی اونها دارن زیاد میشن ولی سرعت رشد صورت خیلی کمتر از مخرجه که در این صورت کسر به سمت صفر میل خواهد کرد . اگر هم جواب یک عدد ثابت مثل c بشه که c مخالف صفر باشه ، به این معنی خواهد بود که توابع f و g دارای سرعت رشد تقریبا یکسان هستند .

یکی دیگه از روش های تعیین پیچیدگی زمانی ، وقتی که پیچیدگی یک الگوریتم به صورت یک رابطه ی بازگشتی باشه ،روش "قضیه ی اصلی" هست که بسیار در محاسبه ی پیچیدگی زمانی الگوریتم ها کاربرد داره . شکل خلاصه ی این قضیه به این صورت هست :

 

به عنوان آخرین مطلب در این جلسه هم میخوایم پیچیدگی زمانی الگوریتم (شبه کد) محاسبه ی فاکتوریل عدد n رو باهم بررسی کنیم که شکل زیر این کار رو انجام میده :

خب دوستان برای این جلسه کافیه .. سعی کردیم در این جلسه درباره ی الگوریتم ها و کارآمدی اونها باهم صحبت کنیم . البته مباحث دیگر مرتبط با الگوریتم ها مربوط به طراحی و تحلیل الگوریتم ها میشه و من فکر میکنم تا همین حد برای ساختمان داده ها کفایت میکنه و به شما توصیه میکنم حتما خودتون هم مطالعه داشته باشید . انشاءالله از جلسه ی بعدی شروع میکنیم به بررسی انواع ساختمان های داده ای و اولین ساختار داده ای مورد بررسی هم "آرایه" خواهد بود.

  ممنونم از توجه شما و خدا یار  و نگهدارتان.

قسمت بعدی قسمت قبلی