سوال:
- چگونه می‌توانیم زمان اجرای یک الگوریتم را محاسبه کنیم؟
- چگونه می‌توانیم دو تا الگوریتم را با هم مقایسه کنیم؟
- چگونه می‌توانیم بگوییم که یک الگوریتم بهینه هست؟
جواب:
تعداد عملیات پایه که الگوریتم با بدترین ورودی اجرا می‌کند.
عملیات پایه می‌توانند یکی از موارد زیر باشند:
- یک انتساب (Assignment)
- مقایسه‌ى دو تا متغییر (Comparison)
- یک محاسبه ریاضی بین دو تا متغیر (Arithmatic Operation)
بدترین ورودی هم، آن ورودیی است که باعث اجرای بیشترین عملیات پایه می‌شود. به عنوان مثال در حلقه زیر با بدترین ورودی بیشترین تکرار 5 است:
n := 5;
loop
get(m);
n := n -1;
until (m=0 or n=0)
و در حلقه زیر با بدترین ورودی بیشترین تکرار n می‌باشد:
get(n);
loop
get(m);
n := n -1;
until (m=0 or n=0)
حالا چطور تعداد عملیات پایه را بشماریم؟ برای ساختارهای مختلف الگوریتم به شرح زیر عمل می‌کنیم:
توالی (Sequence):
P و Q قسمتهای یک الگوریتم هستند.
زمان کل = زمان(P) + زمان(Q)
حلقه (Iteration):
while < condition > loop
P;
end loop
یا
for i in 1..n loop
P;
end loop
زمان کل = زمان<span dir=ltr>x (P)</span> بیشترین تعداد تکرار
شرط (Conditional):
if < condition > then
P;
else
Q;
end if;
زمان کل = زمان(P) اگر شرط برقرار باشد
زمان کل = زمان(Q) اگر شرط برقرار نباشد
روتینهای بازگشتی (Recursive Procedures):
در ادامه بحث "تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر"، در مورد زمان اجرای روتینهای بازگشتی شرح مختصری داده خواهد شد. در اینجا تنها به این نکته بسنده می‌کنم که زمان اجرای این روتینها بسته به اندازه ورودی تابعی (توابعی) لگاریتمی است.
خوب٬ برای نمونه الگوریتم زیر رو در نظر بگیرید:
for i in 1..n loop
for j in 1..n loop
if i < j then
swop (a(i,j), a(j,i)); -- Basic operation
end if;
end loop;
end loop;
تعداد عملیات پایه < <span dir=ltr>n^2</span> = <span dir=ltr>(n * n * 1)</span>
پاسخ با نقل قول