موضوع مقاله: نمادهای توابع رشد الگوریتم‌ها | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # نمادهای توابع رشد الگوریتم‌ها | مقدمه: گاهی‌اوقات بیش از یک الگوریتم برای حل یک مسئله وجود دارد؛ بنابراین بهینه بودن ابزارها حایز اهمیت است. | ## بخش 1: نمادهای توابع رشد الگوریتم‌ها | مهم‌ترین پارامترهای بهینگی یک الگوریتم، میزان حافظه و زمانی است که برای اجرا مصرف می‌کند و این دو پارامتر، معیارهایی برای سنجش کارایی الگوریتم هستند. یکی از روش‌های تحلیل‌زمانی الگوریتم بررسی زمان اجرا در بدترین‌حالت و حالت‌میانگین می‌باشد. توجه کنید که بهترین زمان اجرای الگوریتم اهمیت چندانی ندارد، چرا که این حالت معمولاً برای ورودی با تعداد کم و در شرایط خاص اتفاق می‌افتد و زمان اجرا هم اغلب آنقدر کوتاه است که مهم نیست از چه الگوریتمی استفاده می‌شود. بعضی مواقع پیچیدگی (منظور از پیچیدگی، تابعی است برحسب اندازه ورودی که زمان اجرای الگوریتم را بیان می‌کند. در ادامه بحث به چگونگی محاسبهٔ آن خواهیم‌پرداخت) حالت‌میانگین و بدترین‌حالت با یکدیگر تفاوت چندانی نمی‌کند اما معمولاً پیچیدگی الگوریتم در حالت‌میانگین بهتر از پیچیدگی آن در بدترین‌حالت است؛ چراکه اغلب بدترین‌حالت الگوریتم به‌ندرت اتفاق می‌افتد. با استفاده از پیچیدگی الگوریتم‌ها، می‌توانیم آن‌ها را از نظر میزان کارایی با یکدیگر مقایسه کنیم. | ## بخش 2: نمادهای توابع رشد الگوریتم‌ها | برای مثال، زمان اجرای الگوریتم‌های مرتب‌سازی ادغامی و مرتب‌سازی درجی را مقایسه می‌کنیم. می‌دانیم الگوریتم مرتب‌سازی ادغامی از مرتبه‌ی(O(log n و الگوریتم مرتب‌سازی درجی از مرتبه می‌باشد. همان‌طور که مشاهده می‌شود، برای مقادیر کوچک مانند ۱ یا ۲ الگوریتم مرتب‌سازی درجی سریع‌تر از الگوریتم مرتب‌سازی ادغامی عمل می‌کند اما هرچه مقدار n افزایش می‌یابد، الگوریتم مرتب‌سازی ادغامی بسیار سریع‌تر از الگوریتم مرتب‌سازی درجی عمل می‌کند؛ بنابراین از آنجا که اغلب برای ورودی‌های خیلی بزرگ از الگوریتم‌ها استفاده می‌کنیم، به تحلیل الگوریتم‌ها برای nهای بزرگ می‌پردازیم. در این مقاله سعی شده تا روش‌هایی برای مقایسه زمان اجرای الگوریتم‌ها بیان کنیم تا به درک روشنی از میزان بهینه بودن آن‌ها برسیم. در ابتدا به معرفی علایم قراردادی پرداخته سپس مفاهیم، تعاریف و مثال‌هایی از آن‌ها بیان می‌کنیم. علایمی که ما از آن‌ها برای نشان دادن کران‌های مجانبی استفاده می‌کنیم، معرف توابعی هستند که به آنها توابع رشدمی‌گوییم و دامنه آن‌ها مجموعه‌ای از اعداد طبیعی است. | ## بخش 3: نمادهای توابع رشد الگوریتم‌ها | این علایم عبارت‌اند از: : کران بالای مجانبی : کران پایین مجانبی : کران دوطرف مجانبی نماد تعریف ریاضیاتی این نماد به شکل زیر می‌باشد: یعنی آهنگ رشد تابع (g(n برای مقادیر بزرگ n، بیشتر یا مساوی آهنگ رشد تابع (f(nاست. نماد تعریف ریاضیاتی این علامت به شکل زیر می‌باشد که در آن تابع(g(nکران پایین مجانبی برای تابع (f(nاست. به‌طور مثال: نماد بیانگر کران دوطرف مجانبی است که به صورت زیر تعریف می‌شود: این رابطه بدین معنی است که آهنگ رشدf و g برای مقادیر یزرگ n یکسان است و هیچ‌یک از این دو تابع از دیگری جلو نمی‌زنند. به‌طور مثال زمان اجرای مرتب‌سازی درجی است؛ بنابراین، ، زیرا می‌توان به‌سادگی مقادیر مثبتی برای و یافت که . مثال: ثابت کنید که اثبات: باید نشان داد که نمی‌توان مقادیر مثبتی برای ، و یافت که رابطهٔ برای همه مقادیر برقرار باشد. همچنین تابع در واقع عطف O و است به عبارت دیگر، قضیه:شرط لازم و کافی برای آن است که و . | ## جمع‌بندی | خاصیت تقارنی ترانهاده در تابع‌های رشد تعریف شده خاصیت تقارنی‌ترانهاده به‌صورت زیر وجود دارد: شرط لازم و کافی برای آن است که .