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

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

اسلاید 1 :

ساختمان داده ها و الگوريتم

اسلاید 3 :

مقدمه

به زبان ساده ميتوان گفت الگوريتم مجموعهاي از دستورالعملها است كه اگر به ترتيب دنبال شوند، موجب حل مسأله ميگردند.

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

اسلاید 4 :

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

اسلاید 5 :

برای بررسی یک الگوریتم تابعی به نام T(n) که تابع زمانی الگوریتم نامیده می شود را محاسبه می کنیم
اگر ورودی یک گراف باشد زمان اجرای الگوریتم T(n, m) است که در آن n تعداد رأسها و m تعداد یالهاست
برای محاسبه تعداد اجرای دستورات لازم برای انجام عملیات مورد نظر (T(n)):
زمان مربوط به اعمال جایگزینی (که مقدار ثابتی است)
زمان مربوط به اعمال محاسباتی (که مقدار ثابتی است)
زمان مربوط به تکرار تعدادی دستور یا دستورالعمل (حلقه ها)
زمان مربوط به توابع بازگشتی
محاسبه تعداد تکرار عملیات و توابع بازگشتی اهمیت ویژه ای دارند
زمان اجرای الگوریتم ها (ادامه)

اسلاید 6 :

قطعه برنامه زیر را درنظر بگیرید:
x = 0 ;
for ( i = 0; i < n; i++)
x++;
محاسبه تابع زمانی:
مرتبه اجرای الگوریتم

اسلاید 7 :

قطعه برنامه زیر را درنظر بگیرید:
x = 0 ;
for ( i = 0; i < n; i++)
for ( j = 0; j < n; j++)
x++;
محاسبه تابع زمانی:
مرتبه اجرای الگوریتم

اسلاید 8 :

نماد Big-O

اسلاید 12 :

نماد Big-Omega

اسلاید 14 :

نماد θ

اسلاید 17 :

مرتبه رشد

اسلاید 19 :

معمولا الگوریتمهایی که برای حل مسائل بکار می روند به دو دسته اصلی تقسیم می شوند:
الگوریتم های غیر بازگشتی(ترتیبی)
الگوریتم های بازگشتی
روشهای تحلیل الگوریتم ها

اسلاید 20 :

الگوریتم های ترتیبی