پیچیدگی محاسباتی: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
Nimaganji62 (بحث | مشارکت‌ها) جز ویرایش به‌وسیلهٔ ابرابزار: |
بدون خلاصۀ ویرایش |
||
خط ۶:
== ارزیابی کارایی [[الگوریتم]]ها ==
الگوریتم‌های مختلفی برای حل یک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترین الگوریتم باید معیاری جهت مقایسه کارایی الگوریتم‌ها داشته باشیم.
ارزیابی در دو مرحله انجام می‌شود:
سطر ۲۴ ⟵ ۲۲:
سنجیده می‌شود؛ که رفتار الگوریتم را در زمان اجرا با مجموعه‌ای از ورودی‌های منتخب توصیف می‌کنند.
بعد از پیاده‌سازی الگوریتم با یک [[زبان برنامه‌نویسی]]، آمار حقیقی دربارهٔ زمان و حافظه مصرف شده توسط الگوریتم در حین اجرا جمع آوری می‌شود.
== پیچیدگی زمانی ==
سطر ۴۳ ⟵ ۳۹:
:*;آرایش داده‌های ورودی
زمان اجرای برنامه‌ها به صورت رابطه بین بزرگی سایز ورودی و زمان مورد نیاز برای پردازش ورودی است. زمان اجرا یکی از ملاک‌های مقایسه چند الگوریتم برای حل یک مسئله
منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه
مثلاً دستورهای؛ a=b و؛ c/d-e*; a=b هر کدام یک واحد زمانی را دربردارند.
سطر ۵۹ ⟵ ۵۵:
بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به؛ نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی
بدون فراخوانی برابر یک
هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست آوردن این تابع رشد است.
برای مثال هرچه زبان برنامه‌نویسی([[مترجم (رایانه)]]) به [[زبان ماشین]] نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید.▼
▲برای مثال هرچه زبان برنامه‌نویسی([[مترجم (رایانه)]]) به [[زبان ماشین]] نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید
زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.
برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم‌های الگوریتم به صورت تابعی از اندازه مسئله مشخص می‌شود، برای انجام این کار تعداد تکرار عملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می‌دهد، بدست می‌آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی‌های مختلف با استفاده از نمادها O، Θ وΩ که در بخش بعدی با آن‌ها آشنا می‌شویم، بیان می‌شود.
این متن اصلی مقاله‌است که از کتاب خاصی<ref>بابا محمودی، طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم‌ها، ۱۱۵–۱۵۰. [=صفحات کتاب]</ref> و کتاب دیگری<ref>احمدی، فایل در فایل.</ref> و یک پانویس هم دارد *<ref>این یک پانویس توضیحی‌است.</ref>
== [[زمان اجرای الگوریتم]] ==
[[زمان اجرای الگوریتم|زمان اجرای یک الگوریتم]] از مسائل مهم طراحی الگوریتم
:*;دقیق باشد
سطر ۸۸ ⟵ ۷۵:
:*;پایان پذیر باشد
الگوریتم‌ها توسط زبان برنامه‌نویسی پیاده‌سازی می‌شوند و هر الگوریتم توسط یک برنامه ارائه می‌شود هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد.
سطر ۱۰۴ ⟵ ۹۲:
:*;پارامترهای دیگر که تأثیر ثابت در زمان اجرا دارند.
از این عوامل سرعت سخت‌افزار و نوع کامپایلر به صورت ثابت در زمان اجرای برنامه‌ها دخیل هستند. پارامتر مهم پیچیدگی زمانی الگوریتم است که خود تابعی از اندازه مسئله
برای بررسی الگوریتم تابعی به نام (T(n که تابع زمانی الگوریتم نامیده می‌شود در نظر می‌گیریم که در آن n اندازه ورودی مسئله است. مسئله ممکن است شامل چند ورودی باشد. به عنوان مثال اگر ورودی یک گراف باشد علاوه بر تعداد راس ها(n) تعداد یال‌ها (m)هم یکی از مشخصه‌های داده ورودی
برای محاسبه تابع (T(n برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم:
سطر ۱۱۶ ⟵ ۱۰۴:
:*زمان مربوط به توابع بازگشتی
از موارد ذکر شده در محاسبه (T(n یک الگوریتم محاسبه تعداد تکرار عملیات و توابع بازگشتی اهمیت ویژه‌ای دارند و پیچیدگی زمانی مربوط به این دو
مثال: تعداد کل مراحل برنامه زیر را محاسبه کنید.
سطر ۱۹۲ ⟵ ۱۸۱:
f(n)≤cg(n) برقرار باشد.
این نماد حد بالائی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بدترین حالت و بیشترین زمان اجرا را برای
=== امگا/Ω (حدپائین) ===
سطر ۲۰۱ ⟵ ۱۸۸:
((f(n) ≥ c(g(n) برقرار باشد.
این نماد حد پائینی برای تابع (f(n می‌دهد و وقتی بکار می‌رود که رفتار الگوریتم بهترین حالت و کمترین زمان اجرا را برای مقادیر معین ورودی دارد.
=== تتا/Θ (حدمتوسط) ===
سطر ۲۱۵ ⟵ ۲۰۰:
این نماد حدمتوسطی برای تابع(f(n می‌دهد و زمان اجرای الگوریتم را به صورت میانگینی از تعداد عملیات انجام شده با کلیه نمونه ورودی‌های مسئله نشان می‌دهد.
اگر زمان الگوریتم وابسته به ورودی نباشد با نماد O(۱) نشان داده می‌شود؛ و برای تحلیل الگوریتم باید به اندازه کافی الگوریتم را درک کرده باشیم تا بهترین و بدترین رفتار را تولید و محاسبه کنیم.
چون برآورد رفتار آماری ورودی‌ها امری دشوار است، در اکثر موارد به بدترین حالت قناعت می‌کنیم.
نکته. اگر الگوریتم شامل بخش‌های مختلفی باشد که هر قسمت پیچیدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پیدا کرده و بزرگترین مرتبه را به عنوان پیچیدگی کل الگوریتم در نظر می‌گیریم.
غالباً پیچیدگی (g(n یکی از توابع زیر است: n (پیچیدگی خطی)، log n (لگاریتمی)، n^a (چندجمله‌ای) و a^n که a≥۲ (نمائی).
سطر ۲۴۱ ⟵ ۲۲۲:
* [[شاخه و حد|روش شاخه و حد]]
برای محاسبه پیچیدگی روابط می‌توانید از قضایای زیادی استفاده نمایید که مهم‌ترین آن‌ها [[قضیه اصلی]]([[قضیه اصلی واکاوی الگوریتم‌ها]])
'''برای آنکه مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.
| |||