ساختمان داده - جلسه دوم |
الگوریتم
الگوریتم های مختلفی که روی هر ساختار داده ای پیاده سازی می شوند، توسط دو معیار پیچیدگی حافظه ای و زمان مورد ارزیابی قرار می گیرند. تعریفبه طور خلاصه مجموعه ای از دستوالعمل ها برای حل یک مسئله را الگوریتم می گویند. کلمه الگوریتم از نام ریاضیدان قرن نهم ابوجعفرمحمد ابن موسی الخوارزمی گرفته شده است.
یک الگوریتم پنج خاصیت زیر را باید دارا باشد:
الگوریتم ها قرن ها برای حل مسائلی که بشر با آنها روبرو بوده استفاده می شده اند. تقریبا کلیه برنامه های کامپیوتر، بجز برنامه های کاربردی هوش مصنوعی، دربرگیرنده الگوریتم هستند. مشهورترین الگوریتم در تاریخ، الگوریتم اقلیدسی، مربوط به زمان یونان باستان است که برای محاسبه بزرگترین مقسوم علیه مشترک دو عدد صحیح به کار می رفته است و هنوز در دنیای ریاضی کاربرد دارد. خلق الگوریتم های زیبا، ساده و با کمترین مراحل، یکی از چالش های برنامه نویسی است. نحوه بیان الگوریتمالگوریتم های می توانند با نمادهای مختلفی بیان شوند:
امروزه الگوریتم ها معمولا با استفاده از Pseudo Code در یک زبان برنامه نویسی که معمولا پیاده سازی نشده بیان می شوند. در طی این درس از کدهای ساختگی که در ادامه شرح داده می شوند برای بیان الگوریتم ها استفاده می شود. variable := value اختصاص مقداری به یک متغیر را نشان می دهد. if (condition) then برای بیان تصمیم گیری، اگر شرط برقرار باشد عبارت 1 انجام می گیرد و اگر برقرار نباشد عبارت 2 while (condition) برای نمایش حلقه تکرار، اگر شرط برقرار باشد دستورات تکرار می شوند. repeat until (condition) برای نمایش حلقه تکرار، تا وقتی شرط برقرار نشده باشد دستورات تکرار می شوند. درصورت برقرار بودن شرط از حلقه خارج می شود. for (counter:=value1 to value2 ) برای نمایش تکرار عبارتی به تعداد معینی، شمارنده از مقدار1 شروع شده در هربار تکرار یک واحد به آن اضافه می شود تا به مقدار2 برسد. برای شمارش معکوس به جای to از down to قرار می گیرد. انتهای الگوریتم توسط کلمه end مشخص می شود. مثال. الگوریتم زیر به متغیر x مقادیر 1 تا 10 بجز عدد 5 را اختصاص می دهد. x:=0 ارزیابی کارائی الگوریتم هاالگوریتم های مختلفی برای حل یک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترین الگوریتم باید معیاری جهت مقایسه کارائی الگوریتم ها داشته باشیم. ارزیابی در دو مرحله انجام می شود؛ آنالیز کارائی و اندازه گیری کارائی است. آنالیز کارائی یک تخمین اولیه است با دو معیار پیچیدگی فضائی (space complexity) و پیچیدگی زمانی (time complexity) سنجیده می شود که رفتار الگوریتم را در زمان اجرا با مجموعه ای از ورودی های منتخب توصیف می کنند. بعد از پیاده سازی الگوریـتم با یک زبان برنامه نویسی، آمار حقیقی درباره زمان و حافظه مصرف شده توسط الگوریتم در حین اجرا جمع آوری می شود. پیچیدگی حافظهپیچیدگی حاظه ای میزان فضائی از حافظه است که برنامه برای اجرای کامل به آن نیاز دارد. فضای مورد نیاز در هربرنامه مجموع قسمت های زیر است:
در تحلیل فضای لازم روی تخمین بخش متغیر تاکید نداریم زیرا برای هرمسئله ابتدا باید مشخصات موردی را تعیین کنیم که کار دشواری است. پیچیدگی زمانیزمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم های الگوریتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام این کار تعداد تکرارعملیات اصلی الگوریتم محاسبه می شود و به صورت تابع f(n) (که n تعداد ورودی هاست) بیان می شود. سپس تابع g(n)، که مرتبه بزرگی تابع f(n) را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می دهد، بدست می آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی های مختلف با استفاده از نمادها O ، Θ و Ω بیان می شود. تعریف Big-O (حدبالا) تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیمf(n) = O(g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوریکه از یک n0 به بعد همیشه f(n)≤ cg(n) برقرار باشد. این نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیر معین ورودی دارد تعریف Big-Ω (حدپائین) تابع f(n) را نظر بگیرید که برای کلیه n≥0 است ، می گوئیم f(n) = Ω (g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوریکه از یک n0 به بعد همیشه f(n)≥ cg(n) برقرار باشد. این نماد حد پائینی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد تعریف Big-Θ (حدمتوسط) تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیم f(n) = Θ(g(n)) اگر ثابت های مثبت n0، c1 و c2 وجود داشته باشند به طوریکه از یک n0 به بعد همیشه c1g(n) ≤f(n) ≤ c2g(n) برقرار باشد. این نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی های مسئله نشان می دهد. قضیه. اگر f(n)=amnm+am-1nm-1+…+a1n+a0 در اینصورت f(n)=O(nm) است. مثال. الگوریتم مرتب سازی حبابی را درنظر بگیرید. for (i:=1 to n-1) با درنظر گرفتن عمل مقایسه بعنوان عملگر اصلی، دستور If در الگوریتم فوق (n-1)2 بار تکرار می شود. بنابراین f(n)= (n-1)2=n2-2n+1 و طبق قضیه g(n)=n2 است. بنابراین پیچیدگی الگوریتم فوق برابر با O(n2) می باشد. نکته. اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(1) نشان داده می شود. نکته. باید به اندازه کافی الگوریتم را درک کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم. چون برآورد رفتار آماری ورودی ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می کنیم. نکته. اگر الگوریتم شامل بخش های مختلفی باشد که هر قسمت پیچیدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پیدا کرده و بزرگترین مرتبه را بعنوان پیچیدگی کل الگوریتم درنظرمی گیریم. غالبا پیچیدگی g(n) یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، na (چندجمله ای) و an که a≥2 (نمائی). در زیر مربته اجرائی چند تابع به ترتیب صعودی نوشته شده است. O(1) |