ویکی‌پدیا

پیچیدگی محاسباتی: تفاوت میان نسخه‌ها

نمایش تاریخچه به صورت تعاملی
→ تفاوت قدیمی‌ترتفاوت جدیدتر ←
محتوای حذف‌شده محتوای افزوده‌شده
دیداریویکی‌متن
جز تمیزکاری، + ماژول ابرابزار با استفاده از AWB
ابرابزار
خط ۱۷۶:
T(n)=n(n+1)/2
 
== پیچیدگی حافظه<ref>برگرفته از کتاب ریاضیات گسسته و کاربردهای آن، کنت اچ روزن</ref ==
پیچیدگی حافظه‌ای میزان فضائی از حافظه‌است که برنامه برای اجرای کامل به آن نیاز دارد. فضای مورد نیاز در هربرنامه مجموع قسمت‌های زیر است:<ref>برگرفته از کتاب ریاضیات گسسته و کاربردهای آن، کنت اچ روزن</ref>
 
زیر است:
* بخش ثابت فضا که معمولاً شامل فضای دستورالعمل، فضای متغیرهای با اندازه ثابت و فضای لازم برای ذخیره ورودی و خروجی‌های برنامه‌است.
* بخش متغیر فضا شامل فضای پشته و فضای موردنیاز برای مقادیر متغیرهایی که اندازه آنها بستگی به مسئله و مشخصات ورودی دارد.
سطر ۱۸۹ ⟵ ۱۸۷:
 
=== Big-O (حدبالا) ===
تابع f(n) را برای n≥0n≥۰ در نظر بگیرید. می‌گوئیم((f(n) = O(g(n) است اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
 
f(n)≤cg(n) برقرار باشد.
سطر ۱۹۸ ⟵ ۱۹۶:
 
=== امگا/Ω (حدپائین) ===
تابع (f(n را برای n≥0n≥۰ در نظر بگیرید. می‌گوئیم ((f(n) = Ω(g(n) اگر ثابت مثبت و حقیقی c و عدد صحیح و غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
 
((f(n) ≥ c(g(n) برقرار باشد.
سطر ۲۰۷ ⟵ ۲۰۵:
 
=== تتا/Θ (حدمتوسط) ===
تابع (f(n را برای n≥0n≥۰ در نظر بگیرید. می‌گوئیم((f(n) = Θ(f(n) است اگر ثابت‌های مثبت و حقیقی c و d و عدد صحیح غیر منفی N وجود داشته باشند به طوریکه به ازای تمام مقادیر n≥N:
 
c g(n) ≤f(n) ≤ d g(n) برقرار باشد.
برگرفته از «https://fa.wikipedia.org/wiki/پیچیدگی_محاسباتی»