الگوریتم های مختلفی که روی هر ساختار داده ای پیاده سازی می شوند، توسط دو معیار پیچیدگی حافظه ای و زمان مورد ارزیابی قرار می گیرند.
به طور خلاصه مجموعه ای از دستوالعمل ها برای حل یک مسئله را الگوریتم می گویند. کلمه الگوریتم از نام ریاضیدان قرن نهم ابوجعفرمحمد ابن موسی الخوارزمی گرفته شده است.
تعریف دقیق تر الگوریـم به صورت زیر است:
یک الگوریتم مجموعه ای متناهی از دستورات برای حل یک مسئله خاص توسط انسان یا ماشین است، که ترتیب انجام عملیات در آن مشخص شده و عملیات در زمان معینی خاتمه پیدا می کند. هر دستورالعمل در الگوریتم باید مختصر، دقیق، و صریح باشد.
یک الگوریتم پنج خاصیت زیر را باید دارا باشد:
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)
داده یک نمایش باینری از یک موجودیت منطقی قابل ذخیره سازی در حافظه کامپیوتر است.
داده ها درواقع مقادیری هستند که بعنوان ورودی به یک الگوریتم داده می شود تا پردازشی روی آنها انجام شود.
هر نوع عملیاتی، نظیر محاسبات، مقایسه، جستجو، حذف یا تغییر داده که توسط برنامه روی داده ها انجام می پذیرد پردازش داده محسوب می شود.
داده ها نمایشی از اطلاعات در حافظه می باشند. نحوه نمایش یک داده خاص در حافظه توسط نوع داده (Data Type) آن مشخص می شود. نوع داده مجموعه ای از مقادیر و مجموعه ای از عملیاتی که روی این مقادیر اجرا می شود را تعیین می کند.
نوع داده یک مفهوم ذهنی است که با مجموعه ای از خواص منطقی و اعمال مربوط به آن قابل تعریف است. وقتی نوع داده تعریف شد می توان آن را پیاده سازی کرد.
پیاده سازی می تواند سخت افزاری یا نرم افزاری باشد:
• در پیاده سازی سخت افزاری مدارات لازم برای اجرای عملیات طراحی می شود.
• در پیاده سازی نرم افزاری برنامه ای برای تفسیر رشته های بیتی و انجام عملیات موردنیاز با استفاده از دستورات سخت افزاری نوشته می شود.
وقتی نوع داده پیاده سازی شد برنامه نویس می تواند از آنها برای حل مسائل استفاده کند.
انواع داده ای که به صورت سخت افزاری طراحی می شوند انواع داده ابتدایی (Primitive Data Type) نامیده می شوند. هر کامپیوتری دارای مجموعه ای از انواع داده ابتدایی است.
یک زبان برنامه نویسی سطح بالا امکانات خوبی را برای تعریف نوع متغیر در اختیار برنامه نویس قرار می دهد. تعریف نوع داده متغیر مشخص می کند محتویات حافظه چگونه باید تفسیر شود و کامپایلر را قادر می سازد که عملکرد متناسب با متغیررا تشخیص دهد.
هر زبان برنامه نویسی مجموعه ای از انواع داده را تعریف می کند.
نوع های داده در زبان های برنامه نویسی C و Pascal
|
Data Type |
Pascal |
C |
|---|---|---|
| Character 8 Bit | char | char |
| Signed Integer 8 Bit | shortint | short int |
| Signed Integer 16 Bit | integer | int |
| Signed Integer 32 Bit | longint | long |
| Unsigned Integer 8 Bit | byte | unsigned short int |
| Signed Integer 16 Bit | word | unsigned int |
| Single Precision 32 Bit | single | float |
| Double Precision 64 Bit | double | double |
| Extended Precision 80 Bit | extended | long double |
جدا از جنبه های سخت افزاری، اگر مفهوم نوع داده بر اساس آنچه برنامه نویس می خواهد به صورت نرم افزاری پیاده سازی شود نوع داده انتزاعی (Abstract Data Type) نامیده می شود.
اگر مفهوم نوع داده از توانائیهای سخت افزار جدا شود، تعداد نامحدودی از انواع نوع داده را می توان درنظر گرفت.
مجموعه مقادیر و عملیات روی آنها تشکیل یک ساختار ریاضی را می دهند. نوع داده انتزاعی به مدل ریاضی که یک نوع داده را تعریف می کند اشاره دارد. مدل منطقی یا ریاضی سازماندهی داده ها به یک صورت خاص را ساختمان داده می نامند. ساختمان داده مشخصات عناصر، ارتباط بین آنها و عملیاتی است که روی آنها انجام می شود را تعیین می کند.
1. ساختمان داده خطی : یک ساختمان داده را خطی می گویند هرگاه عناصر آن تشکیل یک دنباله را دهند، به بیان دیگر یک لیست خطی باشند.
برای نمایش لیست خطی دو روش اساسی وجود دارد:
• رابطه خطی بین عناصربه وسیله خانه های متوالی حافظه نمایش داده می شود(آرایه).
• رابطه خطی بین عناصر به وسیله اشاره گرها نمایش داده می شود(لیست پیوندی).
2. ساختمان داده غیر خطی مانند درخت ها و گراف ها
داده هایی که در ساختمان داده ها ظاهر می شوند به وسیله عملیات مشخصی پردازش می شوند. در واقع ساختمان داده خاصی که برنامه نویس برای یک مسئله انتخاب می کند بستگی زیادی به میزان عملیات خاصی دارد که در آن مسئله انجام می شود. برخی از این عملیات که زیاد مورد استفاده قرار می گیرند عبارتند از :
1. پیمایش : دقیقا یک بار دسترسی به کلیه داده های ساختمان داده
2. جستجو : یافتن یک داده یا مجموعه ای از داده ها با شرایط خاصی درون ساختمان داده
3. اضافه : افزودن یک داده جدید به ساختمان داده.
4. حذف : حذف یک داده از ساختمان داده.
5. مرتب سازی : قرار دادن داده ها در کنار هم با یک نظم معین.
6. ادغام : ترکیب داده های دو ساختمان داده مرتب و بدست آوردن یک ساختمان داده مرتب دیگر
7. اتصال : پیوند دو ساختمان داده به یکدیگر
8. کپی : تهیه یک نسخه از ساختمان داده