وبلاگ شخصی حامد پروینی

دانلود مقالات علمی، کتابهای الکترونیکی، ویدئوهای آموزشی

وبلاگ شخصی حامد پروینی

دانلود مقالات علمی، کتابهای الکترونیکی، ویدئوهای آموزشی

آخرین نظرات

دانلود فایل آموزشی تحلیل پیچیدگی زمانی الگوریتم ها

چهارشنبه, ۲۷ خرداد ۱۳۹۴، ۰۳:۰۴ ب.ظ

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

تعریف Big-O (حدبالا)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیمf(n) = O(g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوریکه از یک n0 به بعد همیشه f(n)≤ cg(n) برقرار باشد.

این نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای مقادیر معین ورودی دارد

تعریف Big-Ω (حدپائین)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است ، می گوئیم f(n) = Ω (g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوریکه از یک n0 به بعد همیشه f(n)≥ cg(n) برقرار باشد.

این نماد حد پائینی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد

تعریف Big-Θ (حدمتوسط)

تابع f(n) را نظر بگیرید که برای کلیه n≥0 است، می گوئیم f(n) = Θ(g(n)) اگر ثابت های مثبت n0، c1 و c2 وجود داشته باشند به طوریکه از یک n0 به بعد همیشه c1g(n) ≤f(n) ≤ c2g(n) برقرار باشد.

این نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی های مسئله نشان می دهد.


دانلود کلیه فرمول های مربوط به محاسبه پیچیدگی زمانی الگوریتم ها

دریافت با لینک مستقیم
عنوان: تحلیل پیچیدگی زمانی الگوریتم ها
حجم: 84.2 کیلوبایت
توضیحات: دانلود فایل PDF کلیه فرمول های مربوط به تحلیل پیچیدگی زمانی الگوریتم ها

نظرات  (۱)

خیلی خوب بود.باتشکر
پاسخ:
خواهش میکنم 

ارسال نظر

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.