زمان اجرای الگوریتم: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
FreshmanBot (بحث | مشارکت‌ها) جز ←زمان اجرای الگوریتم: اصلاح فاصله مجازی با استفاده از AWB |
اضافه کردن جدول |
||
خط ۲:
این متن اصلی مقاله‌است که از کتاب خاصی<ref>بابا محمودی، طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم ها، 115-150. [=صفحات کتاب]</ref> و کتاب دیگری<ref>احمدی، فایل در فایل.</ref> و یک پانویس هم دارد *<ref>این یک پانویس توضیحی‌است.</ref>
== زمان اجرای الگوریتم ==
زمان اجرای یک الگوریتم ('''T(n)''' )از مسائل مهم [[طراحی الگوریتم]] می باشد و غالباً [[کارایی الگوریتم ها]] را از روی زمان اجرای آنها بررسی می شود.همان طور که می دانیم الگوریتم عبارتست از : مجموعه ای از دستورها و دستورالعمل ها برای [[حل مسئله]] که شرایط زیر را باید دارا باشد:
* دقیق باشد
* مراحل ان به ترتیب اجرا شود
* پایان پذیر باشد
== انواع زمان اجرا==
زمان اجرا را با تابع O بزرگ محاسبه می کنند.
{| class="wikitable"
|-
! نوع !! زمان'''T(n)''' !! مثال
|-
| ثابت ||O(1) || 10
|-
| لگاریتمی || T(n) = O(log n) ||log n, log(n<sup>2</sup>)
|-
| چند لگاریتمی || T(n) = O((log n)<sup>k</sup>) ||<sup>2</sup>(log n)
|-
| خطی || O(n) || n
|-
| مجذوری || O(n<sup>2</sup>) || n<sup>2</sup>
|-
| چند جمله ای || 2<sup>''O''(log ''n'')</sup> = poly(''n'') || ''n'', ''n'' log ''n'', ''n''<sup>10</sup>
|-
| زیر نمایی(تعریف اول) || ''O''(2<sup>''n''<sup>''ε''</sup></sup>) for all ''ε'' > 0 || ''O''(2<sup>log ''n''<sup>log log ''n''</sup></sup>)
|-
| زیر نمایی(تعریف دوم) || 2<sup>''o''(''n'')</sup> || 2<sup>''n''<sup>1/3</sup></sup>
|-
| نمایی || 2<sup>poly(''n'')</sup> || 2<sup>''n''</sup>, 2<sup>''n''<sup>2</sup></sup>
|-
| فاکتوریل || ''O''(''n''!) || ''n''!
|-
| نمایی دوبل || 2<sup>2<sup>poly(''n'')</sup></sup> || 2<sup>2<sup>''n''</sup></sup>
|}
==روش محاسبه==
الگوریتم ها توسط زبان های [[برنامه نویسی]] پیاده سازی می شوند و هر الگوریتم توسط یک برنامه ارائه میشود هر برنامه نیز مثل الگوریتم زمان اجرای خاص خود را دارد .عوامل دخیل در زمان اجرای برنامه:
* سرعت سخت افزار
| |||