نمادهای توابع رشد الگوریتم‌ها
الگوریتم ابزاری است که از آن برای حل‌مسئله استفاده می‌شود. گاهی‌اوقات بیش از یک الگوریتم برای حل یک مسئله وجود دارد؛ بنابراین بهینه بودن ابزارها حایز اهمیت است. مهم‌ترین پارامترهای بهینگی یک الگوریتم، میزان حافظه و زمانی است که برای اجرا مصرف می‌کند و این دو پارامتر، معیارهایی برای سنجش کارایی الگوریتم هستند. در این مقاله به تحلیل‌زمانی الگوریتم‌ها می‌پردازیم. یکی از روش‌های تحلیل‌زمانی الگوریتم بررسی زمان اجرا در بدترین‌حالت و حالت‌میانگین می‌باشد. توجه کنید که بهترین زمان اجرای الگوریتم اهمیت چندانی ندارد، چرا که این حالت معمولاً برای ورودی با تعداد کم و در شرایط خاص اتفاق می‌افتد و زمان اجرا هم اغلب آنقدر کوتاه است که مهم نیست از چه الگوریتمی استفاده می‌شود. بعضی مواقع پیچیدگی (منظور از پیچیدگی، تابعی است برحسب اندازه ورودی که زمان اجرای الگوریتم را بیان می‌کند. در ادامه بحث به چگونگی محاسبهٔ آن خواهیم‌پرداخت) حالت‌میانگین و بدترین‌حالت با یکدیگر تفاوت چندانی نمی‌کند اما معمولاً پیچیدگی الگوریتم در حالت‌میانگین بهتر از پیچیدگی آن در بدترین‌حالت است؛ چراکه اغلب بدترین‌حالت الگوریتم به‌ندرت اتفاق می‌افتد. از این رو پیچیدگی حالت‌میانگین الگوریتم‌ها همان رفتار مورد انتظار ماست. با استفاده از پیچیدگی الگوریتم‌ها، می‌توانیم آن‌ها را از نظر میزان کارایی با یکدیگر مقایسه کنیم. برای مثال، زمان اجرای الگوریتم‌های مرتب‌سازی ادغامی و مرتب‌سازی درجی را مقایسه می‌کنیم. می‌دانیم الگوریتم مرتب‌سازی ادغامی از مرتبه‌ی(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_7
formula_8 formula_9
نکته: منظور ازformula_10 در واقع formula_11 است.
تعریف ریاضیاتی این علامت به شکل زیر می‌باشد که در آن تابع(g(nکران پایین مجانبی برای تابع (f(nاست.
formula_13
به‌طور مثال:
formula_14
formula_15
بیانگر کران دوطرف مجانبی است که به صورت زیر تعریف می‌شود:
formula_17
این رابطه بدین معنی است که آهنگ رشدf و g برای مقادیر یزرگ n یکسان است و هیچ‌یک از این دو تابع از دیگری جلو نمی‌زنند.
به‌طور مثال زمان اجرای مرتب‌سازی درجی formula_18 است؛ بنابراین، formula_19، زیرا می‌توان به‌سادگی مقادیر مثبتی برای formula_20 و formula_21 یافت که formula_22.
مثال: ثابت کنید که formula_23
اثبات: باید نشان داد که نمی‌توان مقادیر مثبتی برای formula_20 formula_21 و formula_26 یافت که رابطهٔ formula_27 برای همه مقادیر formula_28 برقرار باشد. به‌وضوح به ازای هر مقدار formula_29 و برای مقادیر بزرگ n formula_30.
لم: یک تابع چندجمله‌ای، از مرتبهٔ دقیق جملهٔ با بزرگترین توانش است. یعنی با فرض k>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_48
formula_49
formula_50
تابع رشدformula_4 خاصیت تقارنی دارد.
formula_52 اگر و تنها اگر formula_53.
در تابع‌های رشد تعریف شده خاصیت تقارنی‌ترانهاده به‌صورت زیر وجود دارد:
شرط لازم و کافی برای formula_37 آن است که formula_55.