advertise laitec sharif univercity
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

10000 تومان
دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

دانلود برنامه رنگ آمیزی گراف با الگوریتم عقبگرد در سی شارپ

10000 تومان
دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

دانلود پروژه پایانی طراحی وب سایت مخابرات با Asp.net

48000 تومان
دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

10000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

10000 تومان

نمادهای مجانبی الگوریتم

برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: O ، Ω، Θ و o، ω که هر کدام طبق روش خاصی محاسبه میشوند و در تحلیل الگوریتم کاربرد فراوانی دارند.
نمادهای مجانبی الگوریتم

 

نمادهای مجانبی الگوریتم

برای تخمین زمان اجرای الگوریتم و میزان پیچیدگی آن، از نمادهایی به نام نمادهای مجانبی (حدی) استفاده میشود. این نمادها عباتند از: O ، Ω، Θ و o، ω که هر کدام طبق روش خاصی محاسبه میشوند و در تحلیل الگوریتم کاربرد فراوانی دارند.

زمان اجرای یک الگوریتم Θ (g(n)) است اگر و فقط اگر بدترین حالت زمان O (g(n)) و بهترین حالت (g(n)) باشد.

 

رشد توابع

گوییم رشد تابع f(n) از تابع g(n) بیشتر است اگر  n -> آنگاه f(n) زودتر به ∞ میل میکند. ترتیب رشد زیر برای توابع نام برده قابل اثبات است:

1 < lgn < n< nlgn < n² < n³ < n⁴ < … < 2 < 3ⁿ < 4ⁿ < …< n! < nⁿ

1 یعنی بدون رشد، یعنی به n وابسته نیست. مثلا حلقه ای که 1000 بار اجرا میشود رشدش 1 است.

برای مقایسه رشد توابع میتوان از حد زیر استفاده کرد:

lim -> ∞ f(n)/g(n)

  • اگر جواب حد برابر صفر باشد، نتیجه میگیریم، رشد f از g کمتر است.
  • اگر جواب برابر ∞ باشد، رشد f از g بیشتر است.
  • اگر برابر k 0  باشد، f و g رشد یکسان دارند.

 

نمادهای مجانبی Asymptotic notation

وقتی اندازه ورودی (n) بزرگ باشد، بیان دقیق زمان اجرا برحسب n ضروری نیست زیرا جمله با بزرگترین درجه در زمان موثر است. مثلا اگر زمان اجرای الگوریتمی 2 n³ + n² +n  باشدف به ازای nهای بزرگ فقط n³ مهم است. میتوان با نمادهای مجانبی این تنفسر را بهتر نشان داد. در بیان نمادها فرض میشود که دامنه اعداد طبیعی N={0, 1, 2, …} است.

 

نماد Θ

برای تابع g(n) ،Θ (g(n)) یک مجموعه توابع است که به شکل زیر تعریف میشود:

Θ(g(n)) ={ f(n) : وجود دارد C1 , C2 , n₀ >0 ,   به ازای  n >= n₀ : 0 <=  C1g(n) <= f(n) <= C2g(n) }

یعنی تابع f(n) عضو Θ(g(n)) است یا مینویسیم f(n) = Θ(g(n)) هرگاه اعداد ثابت C1 و C2 وجود داشته باشند که برای nهای به اندازه کافی بزرگ f(n) بین C1g(n) و C2g(n) ساندویچ شود.

بنابراین یک چند جمله ای درجه m که m ثابت است، از مرتبه(nͫ) Θ است و بطور کلی Θ دقیقا مرتبه رشد تابع را تعیین میکند.

 

نماد O 

نماد Θ یک تابع را از بالا و پایین بصورت مجانبی (حدی) محدود میکرد.

نماد O یک کران بالای حدی مشخص میکند:

O(g(n)) ={ f(n) : وجود دارد C , n₀ >0 ,   به ازای  n >= n₀ : 0 <= f(n) <= Cg(n) }

بنابراین O یک کران بالا برای تابع مشخص میکند. ما مینویسیم f(n) = O(g(n))  اگر f(n) عضوی از O(g(n)) باشد.

بطور کلی O(n²) شامل همه توابعی است که رشدشان کمتر یا مساوی n² است.

 

نماد Ω

نماد Ω یک کران پایین حدی برای تابع مشخص میکند:

Ω(g(n)) ={ f(n) : وجود دارد C , n₀ >0 ,  به ازای   n >= n₀ : 0 <=  Cg(n) <=  f(n)  }

بطور کلی (n²) شامل همه توابعی است که رشدشان بیشتر یا مساوی n² است.

 

نماد o ( اُ کوچک)

نماد اُ کوچک، کران بالایی مشخص میکند که اکید است:

o(g(n)) ={ f(n) : به ازای c>0 , وجود دارد n₀ >0 ,   به ازای  n >= n₀ : 0 <= f(n) <= cg(n) }

یعنی نامساوی f(n) <=  Cg(n) باید به ازای همه اعداد مثبت c برقرار باشد، مثلا o(n²) شامل همه توابعی است که رشدشان از n² کمتر است.

 

نماد ω

کران پایین اکید است.

ω(g(n)) ={ f(n) : به ازای c>0 , وجود دارد n₀ >0 ,   به ازای  n >= n₀ : 0 <= cg(n) <= f(n)}

پس (n²)ω شامل همه توابعی است که رشدشان از n² بیشتر است.

 

مقایسه نمادها

تعدی (transtivity)

f(n) = Θ (g(n)) and g(n) = Θ (h(n))  imply  f(n) = Θ (h(n)) 

بجای Θ میتوان سایر نمادها را نیز قرار داد.

 

خاصیت بازتابی (reflexivity)

Θ و O و Ω بازتابی هستند:

f(n) = Θ (f(n))

f(n) = O (f(n))

f(n) = Ω (f(n))

تقارنی (symmetry)

فقط Θ متقارن است:

f(n) = Θ (g(n)) if  and  only  g(n)= Θ (f(n))

 

ترانهاده تقارنی

f(n) = O (g(n)) if  and  only  g(n)= Ω (f(n))

f(n) = o (g(n)) if  and  only  g(n)= ω (f(n))

 

 

 



5
نظرات
  • user avatar سارا:
    ۲۳:۰۹:۴۴ __ ۱۳۹۴/۰۸/۱۳

    سپاسگذارم

  • user avatar علی:
    ۰۹:۰۱:۱۸ __ ۱۳۹۴/۰۸/۱۶

    مرسی خیلی خوب بود

  • user avatar نسیبه:
    ۱۳:۵۷:۵۶ __ ۱۳۹۴/۰۸/۲۶

    خیلی مختصر و مفید بود

  • user avatar saturn:
    ۰۴:۱۵:۱۴ __ ۱۳۹۹/۰۱/۰۵

    سلام, ممنون از زحماتتون اما خواندن متن بدلیل جابجایی نماد های ریاضی بسیار سخت است.

  • user avatar reza:
    ۱۲:۳۸:۴۸ __ ۱۴۰۰/۰۴/۲۹

    سلام مطالب بسیار خوبی بود

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
رشد توابع الگوریتمیمحاسبه و تخمین زمان اجرای الگوریتمروشهای محاسبه زمان اجرای الگوریتمنمادهای مجانبی الگوریتم چه هستند؟چگونگی تخمین زمان اجرای الگوریتم algorithmمقایسه نمادهای مجانبی الگوریتم algorithmنمادهای حدی در الگوریتمزمان اجرای کدهای الگوریتم algorithmنمادهای مجانبی Asymptotic notationتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php