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

حجم فایل : 133.3 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 28
بنام خدا رشد توابع
توابع بازگشتي ساختمان داده ها و الگوريتم ها رشد توابع ---- 2n2+3n+7
---- 3n2 O notation تعريف: تابع f1 از مرتبه O(f2) است ، اگر براي اعداد بزرگ n ( بزرگتر از عددي مثل ، n0) ، ثابت c وجود داشته و در رابطه زير صدق كند:
for all n >= n0 , f1(n) <= c f2(n)
c f2 كران بالاي تابع f1 ناميده مي شود.
f1(n) = 2n2 + 3n + 7 , f2(n) = n2
for all n>=6 , f1(n) < 3 f2(n) f1 ∈ O(f2)
for all n>=1 , f2(n) < f1(n) f2 ∈ O(f1)

O(a0+ a1n + a2n2 +…+annn) f = a0+ a1n + a2n2 +…+axnx  f ∈ O(?)
f /nx = a0/nx + a1/nx-1 +a2/nx-2 + …+ ax
if n∞ : f/nx  ax
if n∞ : f  axnx
پس: ثابت c و عدد بزرگ n0را مي توان يافت که در رابطه زير صدق کنند:
for all n >= n0 , f = a0+ a1n + a2n2 +…+axnx < c nx
f = a0+ a1n + a2n2 +…+axnx ∈ O(nx)
مثال : تعيين ثابت, n0 c براي n2 - 3n< cn2
cn2 > n2 - 3n  c > 1- 3 /n  n0 = 3 , c = 1 Ω Notation تعريف:تابع f1 از مرتبه Ω(f2) است ، اگر براي اعداد بزرگ n ( بزرگتر ازعددي مثل ، n0) ، ثابت c وجود داشته و در رابطه زير صدق كند: for all n >= n0 , f1 >= c f2
c f2 كران پايين تابع f1 ناميده مي شود.
مشابه نماد O مي توان نشان داد که مرتبه توابع چند جمله اي برابر با بزرگترين توان آنهاست:
f = a0+ a1n + a2n2 +…+axnx ∈ Ω(nx)
مثال : تعيين ثابت, n0 c براي n2 - 3n> cn2
cn2 < n2 - 3n  c < 1- 3 /n  n0 = 10 , c = 0.5
Θ Notation تعريف:تابع f1 از مرتبه Θ(f) است ، اگر براي اعداد بزرگ n ( بزرگتر ازعددي مثل ، n0) ، ثابت c1,c2 وجود داشته و در رابطه زير صدق كنند:
for all n >= n0 ,c1f <= f1 <= c2 f
به عبارتي ديگر، تابع از مرتبه Θ(f) است اگر متعلق به O(f) و Ω(f) باشد.
با توجه به مطالب قبلي، مرتبه توابع چند جمله اي برابر با بزرگترين توان آنهاست:
f = a0+ a1n + a2n2 +…+axnx ∈ Θ(nx)
مثال : تعيين ثابت, n0 c1,c2 براي c1n2 <= n2 - 3n <= c2n2
n0 = 10 , c1 = 0.5 , c2 =1 کاربرد نمادهاي O، Ω، Θ در محاسبات در آناليز الگوريتمها گاهي براي سادگي در عبارات محاسباتي اين نماد ها را نيز استفاده مي کنيم. اين نمادها تعاريف مجموعه هاي خاصي هستند و کاربرد آنها در عبارات رياضي ابهاماتي پيش مي آورد.
مثالf(n) = 2n2 + Θ(n)
هدف از اين نوع بيان اين است که f(n) حاصل جمع 2n2 و يک تابع ديگر از مرتبه Θ(n) است. اين تابع مي تواند هر تابعي مانند 3n يا 10n - 13باشد. در اينجا ما به تعريف دقيق تابع مورد نظر اهميتي نمي دهيم و تنها مرتبه آن را مورد توجه قرار مي دهيم الگوريتم Mergesort MERGE-SORT(A, p, r)
1 if p < r
2 then q ← ⌊(p + r)/2⌋
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 ...