تماس درباره   صفحه اصلی
  ساختمان داده > الگوريتم  
 
 

الگوريتم


الگوريتم های مختلفی که روی هر ساختار داده ای پياده سازی می شوند، توسط دو معيار پيچيدگی حافظه ای و زمان مورد ارزيابی قرار می گيرند.

تعريف
نحوه بيان الگوريتم
ارزيابی کارائی الگوريتم ها
پيچيدگی حافظه
پيچيدگي زماني


تعريف

به طور خلاصه مجموعه ای از دستوالعمل ها برای حل يک مسئله را الگوريتم می گويند. کلمه الگوريتم از نام رياضیدان قرن نهم ابوجعفرمحمد ابن موسی الخوارزمی گرفته شده است.
تعريف دقيق تر الگوريـم به صورت زير است:

يک الگوريتم مجموعه ای متناهی از دستورات برای حل يک مسئله خاص توسط انسان يا ماشين است، که ترتيب انجام عمليات در آن مشخص شده و عمليات در زمان معينی خاتمه پيدا می کند. هر دستورالعمل در الگوريتم بايد مختصر، دقيق، و صريح باشد.

يک الگوريتم پنج خاصيت زير را بايد دارا باشد:

1. متناهی بودن. يک الگوريتم بايد هميشه بعد از تعدادی گام به پايان برسد.
2. صراحت. فعلی که در هر قدم الگوريتم انجام می گيرد بايد مختصر، صريح و غير مبهم باشد.
3. ورودی. مقاديری هستند که ابتدا، قبل از شروع، به الگوريتم داده می شوند.
4. خروجی. مقاديری هستند توسط الگوريـم توليد می شود و رابطه مشخصی با ورودی ها دارند.
5. کارائی. دستورات الگوريتم درحد کفايت بايد ساده و دقيق باشند تا يک انسان مانند يک روبات بتواند آنها را با استفاده از قلم و کاغذ بدون احتياج به فکر کردن در زمان معينی انجام بدهد.

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

خلق الگوريتم های زيبا، ساده و با کمترين مراحل، يکی از چالش های برنامه نويسی است.


نحوه بيان الگوريتم

الگوريتم های می توانند با نمادهای مختلفی بيان شوند:

• زبان طبيعی. استفاده از عبارات زبان طبيعی برای بيان الگوريتمی ممکن است باعث طولانی و مبهم شدن آن بشود و برای الگوريـتم های پيچيده و فنی بندرت استفاده می شود.
• زبان های برنامه نويسی. در ابتدا بيان الگوريتم با زبان های برنامه نويسی موجود طرفدار داشت.
• Pseudo Code و فلوچارت. راه های ساختيافته ای برای نمايش الگوريتم، که درحين استقلال از زبان برنامه نويسی خاصی، از ابهام پرهيز می کنند.

امروزه الگوريتم ها معمولا با استفاده از Pseudo Code در يک زبان برنامه نويسی که معمولا پياده سازی نشده بيان می شوند. در طی اين درس از کدهای ساختگی که در ادامه شرح داده می شوند برای بيان الگوريتم ها استفاده می شود.

variable := value

اختصاص مقداری به يک متغير را نشان می دهد.

if (condition) then
   statements1
else
   statements2
end if

برای بيان تصميم گيری، اگر شرط برقرار باشد عبارت 1 انجام می گيرد و اگر برقرار نباشد عبارت 2

while (condition)
   statement
end while

برای نمايش حلقه تکرار، اگر شرط برقرار باشد دستورات تکرار می شوند.

repeat until (condition)
   statement
end loop

برای نمايش حلقه تکرار، تا وقتی شرط برقرار نشده باشد دستورات تکرار می شوند. درصورت برقرار بودن شرط از حلقه خارج می شود.

for (counter:=value1 to value2 )
   statement
end for

برای نمايش تکرار عبارتی به تعداد معينی، شمارنده از مقدار1 شروع شده در هربار تکرار يک واحد به آن اضافه می شود تا به مقدار2 برسد. برای شمارش معکوس به جای to از down to قرار می گيرد.

انتهای الگوريتم توسط کلمه end مشخص می شود.


مثال. الگوريتم زير به متغير x مقادير 1 تا 10 بجز عدد 5 را اختصاص می دهد.

x:=0
while (x < 10)
   if x = 4 then
     x := x + 2
   else
     x := x + 1
   end if
end while
end


ارزيابی کارائی الگوريتم ها

الگوريتم های مختلفی برای حل يک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترين الگوريتم بايد معياری جهت مقايسه کارائی الگوريتم ها داشته باشيم. ارزيابی در دو مرحله انجام می شود؛ آناليز کارائی و اندازه گيری کارائی است.

آناليز کارائی يک تخمين اوليه است با دو معيار پيچيدگی فضائی (space complexity) و پيچيدگی زمانی (time complexity) سنجيده می شود که رفتار الگوريتم را در زمان اجرا با مجموعه ای از ورودی های منتخب توصيف می کنند.

بعد از پياده سازی الگوريـتم با يک زبان برنامه نويسی، آمار حقيقی درباره زمان و حافظه مصرف شده توسط الگوريتم در حين اجرا جمع آوری می شود.


پيچيدگی حافظه

پيچيدگی حاظه ای ميزان فضائی از حافظه است که برنامه برای اجرای کامل به آن نياز دارد. فضای مورد نياز در هربرنامه مجموع قسمت های زير است:

• بخش ثابت فضا که معمولا شامل فضای دستورالعمل، فضای متغيرهای با اندازه ثابت و فضای لازم برای ذخيره ورودی و خروجی های برنامه است.
• بخش متغير فضا شامل فضای پشته و فضای موردنياز برای مقادير متغيرهائی که اندازه آنها بستگی به مسئله و مشخصات ورودی دارد.

در تحليل فضای لازم روی تخمين بخش متغير تاکيد نداريم زيرا برای هرمسئله ابتدا بايد مشخصات موردی را تعيين کنيم که کار دشواری است.


پيچيدگی زمانی

زمان اجرا مقدار زمانی از کامپيوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پيچيدگی زمان الگوريتم ابتدا تعداد قدم های الگوريتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام اين کار تعداد تکرارعمليات اصلی الگوريتم محاسبه می شود و به صورت تابع f(n) (که n تعداد ورودی هاست) بيان می شود. سپس تابع g(n)، که مرتبه بزرگی تابع f(n) را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می دهد، بدست می آيد. در نهايت پيچيدگی الگوريتم برای نشان دادن رفتار الگوريتم با ورودی های مختلف با استفاده از نمادها O ، Θ و Ω بيان می شود.

تعريف Big-O (حدبالا)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيمf(n) = O(g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≤ cg(n) برقرار باشد.

اين نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بدترين حالت و بيشترين زمان اجرا را برای مقادير معين ورودی دارد

تعريف Big-Ω (حدپائين)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است ، می گوئيم f(n) = Ω (g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≥ cg(n) برقرار باشد.

اين نماد حد پائينی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بهترين حالت و کمترين زمان اجرا را برای مقادير معين ورودی دارد

تعريف Big-Θ (حدمتوسط)

تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيم f(n) = Θ(g(n)) اگر ثابت های مثبت n0، c1 و c2 وجود داشته باشند به طوريکه از يک n0 به بعد هميشه c1g(n) ≤f(n) ≤ c2g(n) برقرار باشد.

اين نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوريتم را به صورت ميانگينی از تعداد عمليات انجام شده با کليه نمونه ورودی های مسئله نشان می دهد.


قضيه. اگر f(n)=amnm+am-1nm-1+…+a1n+a0 در اينصورت f(n)=O(nm) است.


مثال. الگوريتم مرتب سازی حبابی را درنظر بگيريد.

for (i:=1 to n-1)
   for (j:=1 to n-1)
     if aj>aj+1 then exchange(aj,aj+1)

با درنظر گرفتن عمل مقايسه بعنوان عملگر اصلی، دستور If در الگوريتم فوق (n-1)2 بار تکرار می شود. بنابراين f(n)= (n-1)2=n2-2n+1 و طبق قضيه g(n)=n2 است. بنابراين پيچيدگی الگوريتم فوق برابر با O(n2) می باشد.


نکته. اگر زمان الگوريتم وابسته به ورودی نباشد با نماد O(1) نشان داده می شود.

نکته. بايد به اندازه کافی الگوريتم را درک کرده باشيم تا بهترين و بدترين رفتار را توليد و محاسبه کنيم. چون برآورد رفتار آماری ورودی ها امری دشوار است، در اکثر موارد به بدترين حالت قناعت می کنيم.

نکته. اگر الگوريتم شامل بخش های مختلفی باشد که هر قسمت پيچيدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پيدا کرده و بزرگترين مرتبه را بعنوان پيچيدگی کل الگوريتم درنظرمی گيريم.


غالبا پيچيدگی g(n) يکی از توابع زير است: n (پيچيدگی خطی)، log n (لگاريتمی)، na (چندجمله ای) و an که a≥2 (نمائی).

در زير مرتبه اجرائی چند تابع به ترتيب صعودی نوشته شده است.

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O( n3) < O(2n) < O(n!)


تمرين روي الگوريتم

سوالات چندگزينه اي درباره ارزيابي الگوريتمها


 


 


صفحه اصلی| PDF| درباره| تماس