زمان اجرای الگوریتم

در نظریه پیچیدگی محاسباتی و علوم کامپیوتر، پیچیدگی زمانی یا زمان اجرایِ یک الگوریتم مقدار زمانی را توصیف می‌کند تا الگوریتم اجرا و متوقف شود. به عبارتی دیگر پیچیدگی محاسباتی منابع زمانی الگوریتم است. پیچیدگی زمانی معمولاً با شمارش تعداد عملیات‌های پایه‌ای که الگوریتم انجام می‌دهد توصیف می‌شود.

زمان اجرای الگوریتم را معمولاً با نماد $T$

به عنوان تابعی از مقدار ورودی نمایش می‌دهیم. به عبارتی دیگر

T_{A}(n)

یعنی مقدار زمانی که طول می‌کشد تا الگوریتم

A

اجرا شود اگر به آن

n

ورودی دلخواه بدهیم. به عدد طبیعی

n

اندازهٔ ورودی می‌گوییم.

در بسیاری از موارد ورودی‌های متفاوت با اندازهٔ یکسان زمان اجرای متفاوتی دارند. در این موارد بدترین حالت یا میانگین این حالات را معیارمان قرار می‌دهیم (بیشینه یا متوسط میان تمام ورودی‌های ممکن به طول $n$

). دلیل این کار این است که در تحلیل یک الگوریتم، رفتار کلی یک الگوریتم برای ما مهم است (و نه یک حالت خاص) در حقیقت تنها مسأله‌ای که برایمان مهم است نرخ رشد زمان اجرا (نسبت به

n

) است.

زمان اجرا از مسائل مهم در طراحی الگوریتم است و برای تحلیل و بررسی میزان کارایی الگوریتم‌ها اهمیت دارد. رفتار مجانبی زمان اجرا بیشترین اهمیت را دارد و معمولاً با نمادهای مجانبی توصیف می‌شود.

تعریف

به شکل دقیق، مقدار $n$

(اندازهٔ ورودی) برابر با تعداد charهایی (مثل صفر و یک) است که به الگوریتم

A

ورودی داده می‌شود. همان طور که گفته شد، این که این بیت‌ها صفر باشند یا یک اهمیتی ندارد و معمولاً بدترین حالت را در نظر می‌گیریم.

فرض کنید $M$

یک مدل محاسباتی مثل یک ماشین تورینگ یا ماشین با دسترسی تصادفی (به انگلیسی: Random Access Machine) باشد که همیشه پایان ‌‌پذیر است. پیچیدگی زمانی

M

تابعی به صورت

T_{M}\colon \mathbb {N} \to \mathbb {N}

است که در آن

T_{M}(n)

تعداد مراحلی است (تعداد اعمال پایه مثل جمع و ضرب و ...) که

M

طی می‌کند (در صورت یک ورودی با طول

n

).

معمولاً مدل محاسباتی ذکر نمی‌شود و به طور پیشفرض RAM فرض می‌شود.

هر عمل پایه (مثل جمع و ضرب و ...) در یک مدل محاسباتی مقدار یکسانی زمان می‌برد و این مقدار (هزینهٔ هر عمل) را واحد زمانی می‌نامیم. پس زمان اجرای الگوریتم برابر با تعداد اعمال پایه‌ای است که این الگوریتم انجام می‌دهد. در نتیجه زمان اجرای هر خط کد (که تابع خاصی را صدا نمی‌زند) ${\mathcal {O}}(1)$

است. از این موضوع برای تحلیل راحت‌تر الگوریتم‌ها استفاده می‌شود.

در پردازنده‌‌های واقعی هر عمل پایه ممکن است به اندازهٔ متفاوتی طول بکشند (مثلاً عمل ضرب کمی کندتر از عمل جمع است) اما در این مدل‌ها از این تفاوت‌های ناچیز صرف نظر می‌کنیم. در کامپیوترهای امروزی هر واحد زمانی حدوداً معادل یک نانوثانیه است ولی این تقریب با پیشرفت تکنولوژی (در سخت‌افزار) تغییر می‌کند (قانون مور).

گاهی در مدل‌های قدیمی هزینهٔ اعمال پایه واحد در نظر گرفته نمی‌شد:

معیار هزینه واحد (پیچیدگی اعمال حسابی) (به انگلیسی: uniform cost criterion): هر عملیات به اندازهٔ یک واحد زمانی (ثابت) هزینه دارد.
معیار هزینه لگاریتمی (پیچیدگی بیتی) (به انگلیسی: logarithmic cost criterion): هزینهٔ انجام هر عملیات با لگاریتم آن متناسب است. مثلاً جمع دو عدد $n$ -بیتی ${\mathcal {O}}(n)$ است.

معیار هزینه لگاریتمی درک و تحلیل الگوریتم را سخت‌تر و سنگین‌تر می‌کرد. همچنین در کامپیوترهای امروزی هر عدد در int یا float ذخیره می‌شود و معمولاً ۳۲ یا ۶۴ بیت دارد و اعمال ساده در آنها هزینهٔ ثابتی دارد ${\mathcal {O}}(1)$

. به همین دلیل معیار هزینه واحد ساده‌تر و به واقعیت نزدیکتر است. به همین دلیل اکثراً از این معیار استفاده می‌شود.

در مقابل اعداد قابل ذخیره در int (هر چند بزرگ) محدود اند $n\leqslant 2^{64}\in {\mathcal {O}}(1)$

. این تناقض از تحلیل کردن الگوریتم‌ها به درستی جلوگیری می‌کند. در معیار هزینه ثابت امکان سوء استفاده وجود دارد. اگر بتوان جمع و ضرب و ... برای اعداد

2^{n}

-بیتی را با هزینهٔ ثابت انجام داد، می‌توان از این قابلیت برای حل سریعتر و راحت‌تر مسائل سوء استفاده کرد؛ در حالی که در واقعیت چنین امری ممکن نیست (دلیل استفاده از معیار هزینه لگاریتمی نیز همین بود).

در نتیجه باید تعریفمان از int را در مدل محاسباتی دقیق کنیم. یک word دنباله‌ای از صفرها و یک‌ها است. اگر طول این دنباله‌ها را ۳۲ فرض کنیم به تعریف int می‌رسیم. اگر طولشان را واحد فرض کنیم (بیت) هزینهٔ هر عمل مثل معیار لگاریتمی می‌شود (مثلاً برای جمع دو عدد $n$

-بیتی باید بیت به بیت جمع کرد و برای هر بیت یک واحد هزینه می‌شود)؛ همچنین اگر طولشان را دلخواه (هر اندازه بزرگ) فرض کنیم به تعریف BigNum می‌رسیم و هزینهٔ هر عمل مثل معیار هزینه واحد می‌شود.

هر عمل پایه (مثل ۴ عمل اصلی و اعمال بیتی منطقی و ...) بر روی هر word به اندازهٔ یک واحد زمانی هزینه دارد. طول هر word و اعمالی که می‌توان روی آنها انجام داد بستگی به تعریف خودمان دارد و در هر موقعیت و زمینه‌ای باید انتخاب مناسب انجام داد تا واقعیت را به شکل دقیق‌تری مدل‌سازی کند.

بی‌توجهی به این موارد از اشتباهات رایج در تحلیل الگوریتم در کتاب‌ها و مقالات است. در این موارد با فرض یک مدل خاص، یک کران پایین برای پیچیدگی محاسباتی اثبات می‌شود و نتیجه گرفته می‌شود که هیچ الگوریتم سریعتری وجود نخواهد داشت در حالی که آن مدل به خوبی کامپیوترهای واقعی را توصیف نمی‌کند.

پیچیدگی بیتی

در تحلیل پیچیدگی محاسباتی اعمال ریاضی هدف ما پیدا کردن پیچیدگی محاسبهٔ یک عمل مثل ضرب است و نمی‌توانیم صورت مسئله (عمل ضرب $n$

-بیتی) را یک عمل پایه فرض کنیم. در موارد مشابه از پیچیدگی بیتی استفاده می‌کنیم. در این مدل هر word یک‌بیتی است و اعمال پایه تنها روی یک بیت اعمال می‌شوند.

پیچیدگی اعمال حسابی

در این مدل هر word تعداد بیت‌های دلخواهی دارد. در الگوریتم‌های محاسبات ماتریسی معمول (مثل روش گاوس) پیچیدگی اعمال حسابی ${\mathcal {O}}(n^{3})$

است ولی پیچیدگی محاسباتی یا بیتی آن ممکن است بسیار فراتر رود (نمایی)، زیرا در طول محاسبه (مثلاً در هر عمل کاهش یا حذف) ممکن است درایه‌های ماتریس به صورت نمایی رشد کنند.

پیچیدگی‌های زمانی متداول

در تحلیل زمانی الگوریتم‌ها به توابع متداولی بر می‌خوریم که در اینجا به ترتیب نرخ رشدشان به آنها اشاره می‌شود.


توصیف مجانبی $T(n)$	مشهور به	مثال برای $T(n)$	الگوریتم به عنوان مثال
${\mathcal {O}}(1)$	زمان ثابت	$T(n)=10$	پیدا کردن میانه در یک آرایهٔ مرتب
${\mathcal {O}}(\alpha (n))$	معکوس تابع آکرمن		اعمال ادغام و جستجو در DSU
${\mathcal {O}}(\lg ^{\star }n)$	لوگ استار
${\mathcal {O}}(\lg ^{(2)}n)={\mathcal {O}}(\lg \lg n)$			اعمال معمول در Heap
${\mathcal {O}}(\lg n)$	لگاریتمی	$T(n)=\lg(n^{2})=2\lg(n)$	جستجوی دودویی
${\mathcal {O}}(\lg ^{k}n)$		$T(n)=\lg ^{2}n$
${\mathcal {O}}(n^{1 \over k})$		$T(n)={\sqrt {n}}$
${\mathcal {O}}(n)$	خطی		پیدا کردن عنصر بیشینه در یک آرایهٔ دلخواه - جستجوی خطی
${\mathcal {O}}(n\lg n)$			Merge sort
${\mathcal {O}}(n^{k})$	چندجمله‌ای	$T(n)=n^{2}$	Bubble sort
${\mathcal {O}}(2^{n})$			الگوریتم Held–Karp
${\mathcal {O}}(k^{n})$	نمایی	$T(n)=1.1^{n}$
${\mathcal {O}}(n!)$	فاکتوریل		حل بی‌خردانهٔ مسألهٔ فروشندهٔ دوره‌گرد

جستارهای وابسته

منابع

↑ Introduction to the Theory of Computation (3rd edition). به کوشش Michael Sipser.
↑ An Introduction to Formal Languages and Automata (6th edition). به کوشش Peter Linz.
↑ Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.
↑ Discrete Mathematics and Its Applications (eighth edition). به کوشش Kenneth H. Rosen.
↑ The Design and Analysis of Computer Algorithms. به کوشش Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.
↑ «the price of abstraction».

بابا محمودی، رمضان. کتاب طلایی پویندگان دانشگاه تحلیل و طراحی الگوریتم‌ها. تهران:نشر ۱۳۹۰.
احمدی، احمد. فایل در فایل. چاپ دوم. تهران: نشر۲، ۱۳۷۵

[:0-1] Introduction to the Theory of Computation (3rd edition). به کوشش Michael Sipser.

[2] An Introduction to Formal Languages and Automata (6th edition). به کوشش Peter Linz.

[:02-3] Introduction to Algorithms (CLRS) (3rd edition). به کوشش Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein.

[4] Discrete Mathematics and Its Applications (eighth edition). به کوشش Kenneth H. Rosen.

[5] The Design and Analysis of Computer Algorithms. به کوشش Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.

[6] «the price of abstraction».