نمادهای توابع رشد الگوریتم‌ها کیست؟ توضیح بده.
الگوریتم ابزاری است که از آن برای حل‌مسئله استفاده می‌شود. گاهی‌اوقات بیش از یک الگوریتم برای حل یک مسئله وجود دارد؛ بنابراین بهینه بودن ابزارها حایز اهمیت است. مهم‌ترین پارامترهای بهینگی یک الگوریتم، میزان حافظه و زمانی است که برای اجرا مصرف می‌کند و این دو پارامتر، معیارهایی برای سنجش کارایی الگوریتم هستند. در این مقاله به تحلیل‌زمانی الگوریتم‌ها می‌پردازیم. یکی از روش‌های تحلیل‌زمانی الگوریتم بررسی زمان اجرا در بدترین‌حالت و حالت‌میانگینمی‌باشد. توجه کنید که بهترین زمان اجرای الگوریتم اهمیت چندانی ندارد، چرا که این حالت معمولاً برای ورودی با تعداد کم و در شرایط خاص اتفاق می‌افتد و زمان اجرا هم اغلب آنقدر کوتاه است که مهم نیست از چه الگوریتمی استفاده می‌شود.بعضی مواقع پیچیدگی (منظور از پیچیدگی، تابعی است برحسب اندازه ورودی که زمان اجرای الگوریتم را بیان می‌کند. در ادامه بحث به چگونگی محاسبهٔ آن خواهیم‌پرداخت)حالت‌میانگین و بدترین‌حالت با یکدیگر تفاوت چندانی نمی‌کند اما معمولاً پیچیدگی الگوریتم در حالت‌میانگین بهتر از پیچیدگی آن در بدترین‌حالت است؛ چراکه اغلب بدترین‌حالت الگوریتم به‌ندرت اتفاق می‌افتد. از این رو پیچیدگی حالت‌میانگین الگوریتم‌ها همان رفتار مورد انتظار ماست.با استفاده از پیچیدگی الگوریتم‌ها، می‌توانیم آن‌ها را از نظر میزان کارایی با یکدیگر مقایسه کنیم. برای مثال، زمان اجرای الگوریتم‌های مرتب‌سازی ادغامی و مرتب‌سازی درجیرا مقایسه می‌کنیم. می‌دانیم الگوریتم مرتب‌سازی ادغامی از مرتبه‌ی(O(log nو الگوریتم مرتب‌سازی درجی از مرتبهformula_1می‌باشد. همان‌طور که مشاهده می‌شود، برای مقادیر کوچک مانند ۱ یا ۲ الگوریتم مرتب‌سازی درجی سریع‌تر از الگوریتم مرتب‌سازی ادغامی عمل می‌کند اما هرچه مقدار n افزایش می‌یابد، الگوریتم مرتب‌سازی ادغامی بسیار سریع‌تر از الگوریتم مرتب‌سازی درجی عمل می‌کند؛ بنابراین از آنجا که اغلب برای ورودی‌های خیلی بزرگ از الگوریتم‌ها استفاده می‌کنیم، به تحلیل الگوریتم‌ها برای nهای بزرگ می‌پردازیم.در این مقاله سعی شده تا روش‌هایی برای مقایسه زمان اجرای الگوریتم‌ها بیان کنیم تا به درک روشنی از میزان بهینه بودن آن‌ها برسیم. در ابتدا به معرفی علایم قراردادی پرداخته سپس مفاهیم، تعاریف و مثال‌هایی از آن‌ها بیان می‌کنیم.علایمی که ما از آن‌ها برای نشان دادن کران‌های مجانبی استفاده می‌کنیم، معرف توابعی هستند که به آنها توابع رشدمی‌گوییم و دامنه آن‌ها مجموعه‌ای از اعداد طبیعی است.این علایم عبارت‌اند از:formula_2 : کران بالای مجانبیformula_3 : کران پایین مجانبیformula_4 : کران دوطرف مجانبیتعریف ریاضیاتی این نماد به شکل زیر می‌باشد:formula_6یعنی آهنگ رشد تابع (g(n برای مقادیر بزرگ n، بیشتر یا مساوی آهنگ رشد تابع (f(nاست. در این‌صورت می‌گوییم(g(n کران بالای مجانبی برای (f(nاست.به‌طور مثال:formula_7formula_8formula_9نکته: منظور ازformula_10 در واقعformula_11است.تعریف ریاضیاتی این علامت به شکل زیر می‌باشد که در آن تابع(g(nکران پایین مجانبی برای تابع (f(nاست.formula_13به‌طور مثال:formula_14formula_15بیانگر کران دوطرف مجانبی است که به صورت زیر تعریف می‌شود:formula_17این رابطه بدین معنی است که آهنگ رشدf و g برای مقادیر یزرگ n یکسان است و هیچ‌یک از این دو تابع از دیگری جلو نمی‌زنند.به‌طور مثال زمان اجرای مرتب‌سازی درجیformula_18است؛ بنابراین،formula_19،زیرا می‌توان به‌سادگی مقادیر مثبتی برایformula_20وformula_21یافت کهformula_22.مثال:ثابت کنید کهformula_23اثبات:باید نشان داد که نمی‌توان مقادیر مثبتی برایformula_20formula_21وformula_26یافت که رابطهٔformula_27برای همه مقادیرformula_28برقرار باشد. به‌وضوح به ازای هر مقدارformula_29و برای مقادیر بزرگ nformula_30.لم:یک تابع چندجمله‌ای، از مرتبهٔ دقیق جملهٔ با بزرگترین توانش است. یعنی با فرض k&gt;0 وformula_31 داریم:formula_32نکته:طبق تعریف،formula_33.همچنین تابعformula_4 در واقع عطف O وformula_3 است به عبارت دیگر،قضیه:شرط لازم و کافی برایformula_36آن است کهformula_37وformula_38.خواص توابع رشد.خاصیت تراگذاری.تابع‌های رشد تعریف شده خاصیت تراگذاری دارند.ازformula_39 وformula_40 نتیجه می‌شودformula_41.ازformula_37 وformula_43 نتیجه می‌شودformula_44.ازformula_45 وformula_46 نتیجه می‌شودformula_47.خاصیت بازتابی.تابع‌های رشد تعریف شده خاصیت بازتابی دارند.formula_48formula_49formula_50خاصیت تقارنی.تابع رشدformula_4 خاصیت تقارنی دارد.formula_52اگر و تنها اگرformula_53.خاصیت تقارنی ترانهاده.در تابع‌های رشد تعریف شده خاصیت تقارنی‌ترانهاده به‌صورت زیر وجود دارد:شرط لازم و کافی برایformula_37آن است کهformula_55.