مرجع دانلود پاورپوینت های درسی

حجم فایل : 112.4 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 53
بنام خدا Algorithmic Complexity Algorithmic Complexity:
Two Key Metrics پيچيدگي مکاني:
حداکثر مقدار حافظه مورد نياز براي انجام محاسبات مورد نظر و ارتباط آن با اندازه ورودي.
پيچيدگي زماني:
حداکثر تعداد محاسبات مورد نياز براي انجام محاسبات مورد نظر و ارتباط آن با اندازه ورودي.
ما ابتدا اين پارامترها را در مورد بازگشت بررسي مي کنيم. Determining Time Efficiency راه حلها:
تجربي: اضافه کردن شمارنده ها جهت اندازه گيري تعداد عمليات انجام شده

تئوري: استفاده از مدل رياضي براي مدل کردن توابع محاسباتي مورد نياز

بازگشت؟ بعضي مسائل از روابط رياضي مناسب بهره مي برند – لذا از اين مسائل شروع مي کنيم. Recursion Time Efficiency: Recurrence Relations محاسبات مورد نياز: سه موضوع
مقدار کار مورد نياز در تکرار فعلي
هزينه مورد نياز براي آماده کردن داده ها قبل از استفاده از بازگشت و بعد از آن
تعداد زير مسائل بازگشتي
بازگشت خطي يا بازگشت درختي
اندازه ورودي زير مسائل بازگشتي
زير مسئله بازگشتي چقدر کوچکتر است. Recursive Binary Search محاسبات مورد نياز در جستجوي بازگشتي
مقدار کار مورد نياز در تکرار فعلي
1 مقايسه (مقايسه ورودي با عنصر وسطي)
1 تنظيم ( تغيير پارامترهاي چپ يا راست)
تعداد زير مسائل بازگشتي
1 زير مسئله (سمت جپ يا راست آرايه)
اندازه ورودي زير مسائل بازگشتي
سايز زير مسئله نصف مسئله اصلي است. Recurrence Relation رابطه بازگشتي عمومي:

T(n) = aT(n/b) + cnk

a = تعداد زير مسائل
b = 1/اندازه زير مسائل
f(n) = کار تکرار فعلي = constant * nk Recurrence: Master Theorem T(n) = aT(n/b) + f (n) where f (n) ≈ nk

a < bk T(n) ~ nk
a = bk T(n) ~ nk lg n
a > bk T(n) ~ nlog b a

Recurrence: Master Theorem T1(n) = 7 T1(n/7)+n
a = 7, b = 7, k = 1 a ? bk 7 == 7
nklgn=> n lgn

T2(n) = 7 T2(n/2)+n2
a = 7, b = 2, k = 2 a ? bk 7 > 22
=> nlogba => nlog27 => n2.81

T3(n) = 7 T3(n/3)+n2
a = 7, b = 3, k = 2 a ? bk 7 < 32
=> nk => n2
Recursive Binary Search T(n) = aT(n/b) + f(n)
a = number of sub problems = 1
b = 1/size of subproblems = 1/(1/2) => 2
f(n) = current iteration work = 2n0 so k = 0

Compare a to bk: 1 vs 2^0 = 1 vs 1
If they are equal, computational cost is:
nk log n = 1 * log n => log n

[Formula can be looked up for >, <, and ==]

Space Complexity چرا ما به پيچيدگي مکاني علاقه منديم؟
اکثر مردم نگران پيچيدگي زماني هستند.
به طو...