پاورپوینت ساختمان داده ها و الگوریتم ها بخش اول رشد توابع توابع بازگشتي

پاورپوینت ساختمان داده ها و الگوریتم ها بخش اول رشد توابع توابع بازگشتي (pptx) 26 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 26 اسلاید

قسمتی از متن PowerPoint (.pptx) :

رشد توابعتوابع بازگشتي ساختمان داده ها و الگوريتم ها رشد توابع ---- 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 MERGE(A, p, q, r) هزينه 1 1 T(N/2) T(N/2) Θ(N) T(N) = 2 T(N/2) + Θ(N) T(1) = c Little o Notation o(g(n)) = {f(n) :∀ c > 0, ∃n0 > 0 |0 ≤ f(n) < cg(n) ∀ n ≥ n0}. تفاوت با O بزرگ: در اين نمادگذاري، کران بالا تابع براي تمام مقادير ثابت c برقرار است. مثال: 2n ∈o(n2) f(n) ∈ o(g(n)) 