مرتبه اجرایی در ساختمان داده

پیچیدگی زمانی و مرتبه اجرایی در ساختمان داده و طراحی الگوریتم از مباحث پایه و مهم در علوم کامپیوتر به حساب می‌آیند. دو مفهوم «پیچیدگی زمانی» و «مرتبه اجرایی» هر دو به محاسبه میزان افت عملکرد یک تابع یا الگوریتم در ازای رشد اندازه ورودی مربوط می‌شوند. پیچیدگی زمانی به انگلیسی «Time Complexity» خطاب می‌شود و گاهی به آن «پیچیدگی اجرایی» هم می‌گویند. در این مطلب سعی شده است تا حد امکان به طور جامع به آموزش مرتبه اجرایی در ساختمان داده پرداخته شود. همچنین برای درک بهتر، مثال‌ها و نمونه سوال‌هایی هم برای اکثر بخش‌های این نوشته ارائه شده‌اند. همچنین در این نوشتار به مرتبه اجرایی حلقه For و While، مرتبه اجرایی توابع بازگشتی، مرتبه اجرایی فاکتوریل و سایر موارد مهم پیرامون مبحث مرتبه اجرایی در ساختمان داده پرداخته شده است.

مرتبه اجرایی در ساختمان داده چیست ؟

در برنامه نویسی برای پیاده‌سازی و ایجاد برنامه‌های نرم افزاری در اکثر مواقع الگوریتم‌های مختلفی وجود دارند که کار یکسانی انجام می‌دهند؛ اما هر یک از این الگوریتم‌ها زمان اجرا و سرعت متفاوتی دارند. بنابراین، در صورتی که چند الگوریتم برای پیاده‌سازی یک برنامه قابل استفاده باشد، لازم است ملاکی معتبر برای مقایسه آن‌ها وجود داشته باشد تا بتوان الگوریتم بهینه را مشخص کرد. یک راه این است که زمان اجرای الگوریتم ملاک قرار داده شود.

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

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

می‌توان میزان رشد زمان اجرای این برنامه را نسبت به افزایش اندازه ورودی روی نمودار نشان داد؛ به‌گونه‌ای که محور x نشان دهنده اندازه ورودی و محور y هم زمان اجرا به ازای هر ورودی باشد. در این صورت، مشخص می‌شود که میزان رشد زمان اجرا نسبت به افزایش اندازه ورودی دارای نظم خاصی است و از تابع مشخصی تبعیت می‌کند. این نمودار و تابع ممکن است ثابت، خطی یا سهمی باشد. به این تابع، پیچیدگی زمانی می‌گویند.

مرتبه اجرایی در ساختمان داده روش و رویکردی ریاضیاتی برای نمایش نسبت رشد اندازه ورودی به رشد زمان اجرا یا همان تابع و نمودار بدست آمده در این خصوص است. برای نمایش مرتبه اجرایی در ساختمان داده از «نمادها» (Notation) استفاده می‌شود. یکی از رایج‌ترین نمادها برای مرتبه اجرایی در ساختمان داده، «نماد O بزرگ» (Big O Notation) است که در ادامه این مقاله به آموزش آن و ۲ نماد رایج دیگر پرداخته می‌شود. مثلاً مرتبه اجرایی خطی در ساختمان داده را می‌توان به صورت $$O\left(n\right)$$ نشان داد. در تصویر فوق، مرتبه اجرایی یا همان پیچیدگی‌های اجرایی مختلف در ساختمان داده با نماد O بزرگ نمایش داده شده است.

پیچیدگی اجرایی در ساختمان داده چیست ؟

پیچیدگی یک الگوریتم به تابعی گفته می‌شود که خروجی آن، مدت زمان اجرای الگوریتم و ورودی آن، اندازه داده‌های ورودی است. در ساختمان داده معمولاً تعداد داده‌های ورودی با n نمایش داده می‌شود. در واقع تابع پیچیدگی اجرایی، مدت زمان اجرای به کار گرفته شده توسط الگوریتم را برحسب تعداد داده‌های ورودی n اندازه‌گیری می‌کند. در جدول زیر برخی از انواع رایج پیچیدگی اجرایی آمده است:

مفهوم T(n) در ارتباط با نماد O بزرگ O(n) چیست؟

در بحث الگوریتم‌ها، استفاده معمول از نماد $$T$$ برای نمایش پیچیدگی زمانی الگوریتم به کار گرفته می‌شود. $$T$$ یک تابع به حساب می‌آید. ورودی این تابع اندازه ورودی الگوریتم و خروجی آن زمان اجرای الگوریتم (در بدترین حالت) برای آن ورودی با اندازه مربوطه است. بنابراین، $$T\left(n\right)$$ یک عدد است؛ عددی که به وسیله تابع $$T$$ در زمان دریافت عدد $$n$$ بازگردانده می‌شود. این عدد، زمان اجرای الگوریتم برای ورودی با اندازه $$n$$ است.

حرف $$O$$ در $$O\left(n\right)$$ یک تابع نیست. این در واقع همان «نماد O بزرگ» یا «Big O Notation» است. در واقع، $$O\left(n\right)$$ نمادی از کلاس و دسته تمام توابعی به حساب می‌آید که (به‌طور مجانبی) حداکثر با سرعت یکسانی با تابع خطی $$f\left(n\right)=n$$ رشد می‌کند.