پیچیدگی زمانی یک الگوریتم

الگوریتم چیست؟

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

بدیهی است که ما می خواهیم مشکل را به کارآمدترین راه حل کنیم. به همین دلیل است که ما به ارزیابی این روش ها نیاز داریم.

دو تخمین پرکاربرد عبارتند از: عملکرد یا پیچیدگی زمانی (مدت زمانی طول می کشد، یا چند عملیات باید انجام شود تا نتیجه حاصل شود) و کارایی یا پیچیدگی فضا (روش ما از چه تعداد منبع اضافی یا ذخیره سازی در حین اجرا استفاده می کند).

در این مقاله ما بر پیچیدگی زمانی یک الگوریتم به عنوان تابعی از اندازه ورودی تمرکز خواهیم کرد.

برای وضوح، پیچیدگی زمانی به معنای زمان واقعی (بر حسب ثانیه بر ثانیه) مورد نیاز برای اجرای کد واقعی نیست، بلکه به معنی تعداد دفعاتی است که یک دستور/عملیات اجرا می شود.

چگونه پیچیدگی زمانی را تخمین بزنیم؟ نماد O بزرگ

Big O، همچنین به عنوان نماد O بزرگ شناخته می شود، معمولا به عنوان راهی برای نشان دادن پیچیدگی الگوریتم استفاده می شود.

Big O مشخص می کند که چگونه عملکرد الگوریتم شما با افزایش اندازه ورودی تا بی نهایت تغییر می کند.

نماد O بزرگ یک نماد ریاضی است که رفتار محدود کننده یک تابع را زمانی که آرگومان به سمت یک مقدار یا بی نهایت خاص تمایل دارد، توصیف می کند. Big O عضوی از خانواده ای از نمادها است که توسط پل باخمن، ادموند لاندو و دیگران اختراع شده است، که در مجموع آنها را نماد Bachmann-Landau یا نماد مجانبی می نامند. حرف O توسط باخمن به معنای Ordnung به معنای ترتیب تقریب انتخاب شد.
(تعریف ویکی پدیا از O-notation)

اوه – او – ث

Big O، Big Omega یا Ω و Big Theta یا Θ نمادهایی هستند که برای بیان پیچیدگی محاسباتی یک الگوریتم استفاده می شوند. در ادامه این مقاله ما بر روی Big O تمرکز خواهیم کرد، اما در اینجا خلاصه ای از معنای هر نماد آورده شده است:

بدترین حالت، بهترین حالت و سناریوهای مورد متوسط

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

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

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

ممکن است برای برخی از الگوریتم ها بدترین و بهترین حالت وجود نداشته باشد. برای مثال، مرتب سازی ادغام همیشه بدون در نظر گرفتن مجموعه داده، O(nLogn) را انجام می دهد.

به اختصار،

• بهترین حالت اگر روش ما حداقل تعداد مراحل را روی داده های ورودی n عنصر انجام دهد.
• در بدترین حالت اگر تابع حداکثر تعداد مراحل را روی داده های ورودی با اندازه n انجام دهد.
• در صورتی که الگوریتم تعداد متوسطی از مراحل را روی مجموعه ورودی از n عنصر اجرا کند.

با این حال، ما نباید به مواردی علاقه مند باشیم که پیچیدگی زمانی الگوریتم ما به اندازه کافی خوب باشد، اگر مجموعه ورودی، مثلاً، مرتب باشد. ما معمولاً به بدترین سناریو اهمیت می دهیم، بنابراین می توانیم پیچیدگی زمانی داده شده را بدون توجه به ویژگی های داده ورودی تضمین کنیم.

پیچیدگی‌های زمانی رایج، پشته از سریع‌تر به کندتر رتبه‌بندی می‌شود

1. O(1) – ثابت.
   زمان اجرا بر اساس اندازه ورودی n نیست، در صورت اندازه ورودی به طور مستقل اجرا می شود (برای مثال، دسترسی به عنصر یک آرایه).

2. O(log(log n)) – لگاریتمی دوگانه.
   جستجوی درون یابی؛ درختان Van Embe Boas (VEBT).

3. O(log n) – لگاریتمی. الگوریتم‌هایی که ورودی اولیه را به دو قسمت (یا بیشتر) تقسیم می‌کنیم و سپس مشکل را فقط در یک قسمت حل می‌کنیم (برای مثال، جستجوی باینری).

4. O(n) – خطی. هر الگوریتمی با یک حلقه که در اندازه ورودی n تکرار می شود (به عنوان مثال، یافتن عنصر حداکثر در یک آرایه، چاپ تمام مقدار در آرایه، یافتن یک عنصر در یک مجموعه).

5. O(n∙log n) – شبه خطی. هر الگوریتم با استراتژی تقسیم و غلبه (مسئله را به مسائل فرعی از همان نوع تقسیم کنید، به صورت بازگشتی آن مسائل فرعی را حل کنید و پاسخ ها را ترکیب کنید). برای مثال، مرتب‌سازی ادغام، مرتب‌سازی پشته‌ای.

6. O(n^2) – درجه دوم. هر الگوریتمی با دو حلقه تو در تو که از طریق مجموعه ورودی تکرار می‌شوند (مثلاً مرتب‌سازی حبابی، مرتب‌سازی درج).

7. O(n^3) – مکعب. هر الگوریتم با سه حلقه تو در تو که در مجموعه ورودی تکرار می شود.

8. O(2^n) – نمایی. تمام زیر مجموعه های یک مجموعه داده شده را بیابید. مشکل فروشنده دوره گرد با استفاده از برنامه نویسی پویا

9. O(n!) – فاکتوریل. همه جایگشت های ممکن یک رشته داده شده را پیدا کنید. مشکل فروشنده دوره گرد با استفاده از جستجوی brute-force.

ساختارهای داده و پیچیدگی زمانی

پیچیدگی الگوریتم به شدت به ساختارهای داده ای که ما می خواهیم استفاده کنیم بستگی دارد. حدس درست ساختار داده ممکن است منجر به عملکرد بهتر شود.

ساختار داده نحوه ذخیره، دسترسی و نگهداری داده ها را تعریف می کند. بسته به اینکه از کدام عملیات بیشتر در الگوی خود استفاده کنیم، ممکن است به ساختار داده های متفاوتی برای بهبود پیچیدگی زمانی نیاز داشته باشیم.

رایج ترین عملیات عبارتند از: جستجو، دسترسی، درج، حذف.

در هر ساختار داده، چنین عملیاتی به زمان متفاوتی برای اجرا نیاز دارد و هزینه آن بر حسب Big-O ارزیابی می شود. با دانستن هزینه هر عملیات، ممکن است پیچیدگی زمانی الگو را بهبود بخشیم، به سادگی به یک ساختار داده تغییر می دهیم که در آن هزینه این عملیات کمتر از اجرای فعلی ما باشد.

می توانید از معروف ترین برگه تقلب زیر ساختارهای داده مختلف و پیچیدگی های آنها استفاده کنید

نتیجه

در این پست سعی کردیم نکات کلیدی در مورد پیچیدگی زمانی الگوریتم ها را درک کنیم و در اینجا چند نکته وجود دارد:

• پیچیدگی زمانی به معنای زمان واقعی بر حسب میلی ثانیه نیست، بلکه به معنای تعداد عملیات ابتدایی است که الگوبرداری انجام می دهد.
• هنگام تجزیه و تحلیل پیچیدگی زمانی، همیشه بدترین سناریو را تخمین بزنید
• پیچیدگی زمانی ممکن است با استفاده از ساختار داده های مختلف که کمترین هزینه را برای عملیات دارد که اغلب در الگوی ما استفاده می شود بهبود یابد.

ممنون که تا آخر خواندید! خوشحال می شوم به سوالات در نظرات پاسخ دهید!