پاورپوینت ساختمان داده ها

بخشی از پاورپوینت

اسلاید 1 :

ساختمان داده ها

اسلاید 2 :

دو فاکتور مهم در ارزیابی الگوریتم:
حافظه مصرفی
زمان اجرا

محاسبه زمان اجرای الگوریتم:

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

پیچیدگی زمانی

اسلاید 3 :

مثالی از شمارش خطوط برنامه برای بررسی پیچیدگی اجرایی:

نکته 1: در محاسبه پیچیدگی در عمل تعداد اجرای عملیات اصلی مدنظر است و به ندرت تعداد کل مراحل یا گامهای برنامه را نیاز است که بدانیم.

اسلاید 4 :

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

اسلاید 5 :

نکته 2: برای محاسبه تعداد عملیات اصلی بدلیل وجود حلقه گاهی از
برای محاسبات استفاده میشود. خواص شامل:
مقدار a ثابت است و به i وابسته نیست

اسلاید 6 :

اگر قدر نسبت بین صفر و یک باشد: جمع تصاعد هندسی=

اسلاید 8 :

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

اسلاید 9 :

محاسبه مرتبه اجرای الگوریتم معادل یافتن عبارت هم ارز با زمان اجرای دقیق و گام به گام الگوریتم است. مثلا عبارت هم ارز با T(n)=5n²+2n+4 هم ارز با عبارت 5n² است و بدان معناست که زمانی که n خیلی زیاد باشد مقدار 2n+4 قابل صرف نظر است و تنها 5n² را درنظر میگیریم.

معادل ریاضی مرتبه اجرای الگوریتم یافتن بیگ اٌ ، امگا و یا تتا برای زمان معادله اجرای الگوریتم است.

اسلاید 10 :

F(n) بیگ اٌی g(n) است یا f(n)=O(g(n)) هرگاه:

F(n) امگای g(n) است یا f(n)=Ω(g(n)) هرگاه:

F(n) امگای g(n) است یا f(n)=Ѳ(g(n)) هرگاه:

F(n) اٌی g(n) است یا f(n)=o(g(n)) هرگاه:

F(n) اامگای کوچک g(n) است یا f(n)=ω(g(n)) هرگاه:

اسلاید 14 :

مثالهای بیشتر:

پیچیدگی از چپ به راست درحال افزایش است:
افزایش مقدار پیچیدگی

اسلاید 17 :

مشخصه الگوریتمهای بازگشتی:

مزایا: سورس کوتاه، راحتی تدوین و پیاده سازی برخی الگوریتمها که روند حل آنها بازگشتی است و تعداد کمتر دستورات.

معایب: اتلاف حافظه به دلیل استفاده از پشته که مراحل بازگشت را نگه دارد، سرعت اجرا در اکثر الگوریتمهای بازگشتی کمتر از الگوریتم غیربازگشتی است.

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

اسلاید 18 :

مثال: محاسبه مرتبه اجرایی تابع فاکتوریل:

روش اول: به ازای n=4 محاسبه میکنیم. که کلا تابع fact(4)، 4 بار اجرا میشود. پس در حالت کلی به ازای n، n بار تابع فراخوانی میشود. پس مرتبه اجرای الگوریتم بازگشتی محاسبه فاکتوریل T(n)=O(n) می باشد.
در واقع مرتبه تعداد گره های درخت بازگشت همان مرتبه الگوریتم است.

اسلاید 19 :

مثال: محاسبه مرتبه اجرایی تابع فاکتوریل:

روش دوم: ابتدا تابع پیچیدگی محاسبه میشود:
سپس معادله را از روشهایی چون جایگزینی حل میکنیم:
T(n)=O(n)

اسلاید 20 :

دو نوع شیوه الگوریتم نویسی برای حل مسائل وجود دارد:

نوع تقسیم و غلبه: روش حل بالا به پایین (top-down) است که در این روش یک مسئله بزرگ به مسائل کوچکتر تقسیم میشود و هر مسئله کوچکتر در صورت لزوم مجددا به مسائل کوچکتر تقسیم میشوند. الگوریتمهای بازگشتی در این رده قرار میگیرند.

عیب روش: در برخی موارد ممکن است یک مسئله کوچک چندین بار حل شود.

نوع پویا: روش جزء به کل یا پایین به بالاست. الگوریتمهای این دسته بازگشتی نیستند. در این دسته الگوریتمها ابتدا مسائل کوچکتر حل میشوند و به تدریج به مسائل بزرگتر میرسیم طوریکه در پایان کل مسئله حل شده.

مزیت: در این روش محاسبات تکراری نداریم.

انواع الگوریتم