صفحه محصول - پاورپوینت با عنوان رشد توابع توابع بازگشتی

لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : 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