ساختمان داده - جلسه دوم

الگوریتم

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

---

تعریف

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

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

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

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)) اگر ثابت های مثبت n₀ و c وجود داشته باشند به طوریکه از یک n₀ به بعد همیشه f(n)≤ cg(n) برقرار باشد.

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

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

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

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

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

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

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

---

قضیه. اگر f(n)=a_mn^m+a_m-1n^m-1+…+a₁n+a₀ در اینصورت f(n)=O(n^m) است.

---

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

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

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

---

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

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

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

---

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

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

O(1)2) < O( n³) < O(2ⁿ) < O(n!)

---