پیچیدگی زمانی و پیچیدگی مکانی یک الگوریتم توضیح داده شده است
دو برنامه را تصور کنید که دقیقاً کار یکسانی انجام میدهند. اگر به هر کدام هزار رکورد بدهید، نمیتوانید آنها را از هم تشخیص دهید. اما اگر یک میلیارد رکورد به آنها بدهید، یکی قبل از اینکه کلید Enter را رها کنید، کار را تمام میکند، در حالی که دیگری سهشنبهی آینده هنوز مشغول کار است.
همان لپتاپ. همان دادهها. چیزی که آنها را از هم جدا میکند، پیچیدگی زمانی است، که فقط نامی برای سرعت افزایش حجم کار یک الگوریتم با افزایش ورودی آن است.
ما بررسی خواهیم کرد که این اصطلاح در واقع به چه معناست، چگونه نمادگذاری Big O آن را مینویسد، چگونه میتوان آن را از یک قطعه کد واقعی استخراج کرد و پیچیدگی فضا کجا مطرح میشود. سپس، در پایان، جایی که همه اینها دیگر تکالیف نیستند و شروع به هزینه کردن پول واقعی میکنند: قراردادهای هوشمند.
پیچیدگی زمانی یک الگوریتم چیست؟
برای لحظهای ثانیهها را فراموش کنید. پیچیدگی زمانی، گامها را میشمارد. مقایسهها، انتسابها، کمی محاسبات اینجا و آنجا، و شما مجموع را به عنوان تابعی از n مینویسید، که اندازه ورودی است.
در اینجا به کسلکنندهترین تابع قابل تصور میپردازیم:
پایتون def print_all(items): برای آیتم در آیتمها: print(item)
ده مورد؟ ده بار تکرار در یک حلقه. ده هزار؟ ده هزار تکرار.
کار در یک خط مستقیم در کنار ورودی بالا میرود، بنابراین آن را O(n) مینامیم.
حالا، شاید هر سفر واقعاً به جای یک عمل، سه عمل کوچک هزینه داشته باشد. خب، میشود ۳ پنی. راستش را بخواهید، کسی اهمیتی نمیدهد، چون دو برابر کردن لیست، کار را دو برابر میکند، و آن منحنی رشد همان چیزی است که ما میخواهیم. عدد دقیق عمداً حذف میشود.
به همین دلیل است که هر دوره DSA و نیمی از مصاحبههای کدنویسی روی پیچیدگی زمانی تمرکز میکنند. اگر بتوانید پیچیدگی یک الگوریتم را با نگاه کردن به آن بخوانید، میتوانید حدس بزنید که روی دادههای ورودی که هرگز فرصت آزمایش آنها را نداشتهاید، چگونه رفتار خواهد کرد. که در عمل، بیشتر دادهها همین هستند.
چرا زمان اجرا معیار ضعیفی برای یک الگوریتم است؟
پس چرا فقط با یک تایمر اجرا نمیشود؟ خیلیها این کار را میکنند، و من متوجه هستم. نکته این است که زمان اجرا، انبوهی از چیزهایی را که الگوریتم شما هیچ ارتباطی با آنها ندارد، به خود جذب میکند:
- سختافزار. لپتاپ پنج ساله من و یک ابررایانه کاملاً نو، اعداد کاملاً متفاوتی را برای یک اسکریپت به شما میدهند.
- زبان برنامهنویسی. اگر حلقهی یکسانی را در C و پایتون بنویسید، ممکن است یک فاصلهی ۱۰ برابر یا بیشتر ببینید.
- بار سیستم. یک بهروزرسانی پسزمینه شروع به کار میکند، جمعآوریکنندهی زباله از خواب بیدار میشود، حافظهی پنهان (cache) غیرفعال است. نتیجهی شما تغییر میکند.
- هر ورودی که گرفتید. مرتبسازیای که روی دادههای تقریباً مرتبشده پرواز میکند، میتواند روی دادههای درهمریختهشده بخزد.
یک کرونومتر به شما یک بار روی یک جعبه با یک ورودی اجرا میدهد. اگر از آن حدود ۱۰۰ برابر دادهها را بپرسید، چیزی دریافت نمیکند.
تعداد گامها تغییر نمیکند. الگوریتم یکسان، ورودی یکسان، و چه Rust روی یک سرور رک باشد و چه جاوا اسکریپت روی گوشی کسی، تعداد گامهای یکسانی دریافت میکنید. به همین دلیل است که پیچیدگی زمانی، یک رقابت منصفانه بین دو راهحل است، قبل از اینکه چیزی را بنچمارک کنید. من هنوز هم بعد از آن، برای اینکه ارزشش را داشته باشد، بنچمارک میکنم. این فقط یک سوال متفاوت است.
توضیح نمادگذاری O بزرگ و سایر نمادهای مجانبی
کتابهای درسی این را نمادگذاری مجانبی مینامند، که از آنچه هست بدتر به نظر میرسد. شما اجازه میدهید n بسیار بزرگ شود و دیگر به چیزهای کوچک اهمیت نمیدهید، بنابراین ضرایب ثابت و ورودیهای کوچک حذف میشوند و فقط منحنی رشد باقی میماند. سه مورد از آنها ارزش دانستن دارند:
| نمادگذاری | آنچه توصیف میکند | معنی ساده | مثال |
|---|---|---|---|
| O بزرگ، O(f(n)) | حد بالا | الگوریتم سریعتر از f(n) رشد نمیکند. | جستجوی خطی O(n) است. |
| بیگ-امگا، Ω(f(n)) | حد پایین | این الگوریتم حداقل به f(n) کار نیاز دارد. | هر نوع مرتبسازی مقایسهای Ω(n log n) است. |
| تتای بزرگ، Θ(f(n)) | تنگ و بسته | تطابق مرزهای بالا و پایین | مرتبسازی ادغامی برابر با Θ(n log n) است. |
در عمل، حدود ۹۵٪ مواقع نماد O بزرگ را خواهید شنید. این نماد یک حد بالا تعیین میکند، به این معنی که زمان اجرا سریعتر از نرخ داخل پرانتز رشد نخواهد کرد. اولین بررسی کد من در یک کار واقعی، توسط یک توسعهدهنده ارشد انجام شد که در کنار یک حلقه تو در تو نوشت: "O(n²), pls fix" و منظور آنها این بود که پیچیدگی زمانی در بدترین حالت، درجه دوم است و لیست قرار است خیلی طولانیتر شود.
امگا و تتا بیشتر در دروس دانشگاهی در مورد تحلیل الگوریتمها وجود دارند، و فکر نمیکنم سالهاست که هیچکدام را سر کار تایپ کرده باشم. O بزرگ برنده میشود چون به چیزی که مردم واقعاً در یک جلسه میپرسند پاسخ میدهد، یعنی «اگر ترافیک سه برابر شود، اوضاع چقدر بد میشود؟»
یک نکته فنی وجود دارد که مدتی من را گیج کرد. از آنجایی که O بزرگ فقط یک سقف است، یک تابع O(n) نیز O(n²) است، به طور دقیق، همانطور که یک فرد 1.5 متری "زیر 1.7 متر" است. درست و بیفایده. هر کسی محکمترین حدی را که میتواند توجیه کند، نقل میکند و من هم همین کار را خواهم کرد.

کلاسهای رایج پیچیدگی زمانی به همراه مثال
کلاسهای زیادی در کد واقعی نخواهید دید، اگر کلاسهای ترسناک را هم حساب کنید، شاید هفت تا باشند. هزینه تقریبی هر کدام با n = 1000 به این صورت است:
| کلاس | نام | مثال معمول | عملیات در n = ۱۰۰۰ |
|---|---|---|---|
| اُ(1) | ثابت | فهرست آرایه، جستجوی جدول هش | ۱ |
| O(log n) | لگاریتمی | جستجوی دودویی | ~10 |
| O(n) | خطی | اسکن کردن یک لیست | ۱۰۰۰ |
| O(n log n) | خطیمشی | مرتبسازی ادغامی، مرتبسازی سریع (میانگین) | حدود ۱۰،۰۰۰ |
| O(n²) | درجه دوم | حلقههای تو در تو، مرتبسازی حبابی | ۱,۰۰۰,۰۰۰ |
| O(2ⁿ) | نمایی | فیبوناچی بازگشتی ساده | بیشتر از اتمهای موجود در جهان |
| اُ(ن!) | فاکتوریل | فروشنده سیار با تجربه و مهارت بالا | حتی بزرگتر |
O(1): زمان ثابت
چه دیکته پایتون شما ده کلید داشته باشد و چه ده میلیون، استخراج یکی به یکی هزینه دارد، و خواندن موارد[5] از یک لیست نیز همینطور. این مسطح بودن، کل نکته زمان ثابت است.
O(log n): زمان لگاریتمی
من اینها را به عنوان الگوریتمهای «حدس زدن عدد بین ۱ تا ۱۰۰» در نظر میگیرم، که در آنها هر حدس، نیمی از عدد باقیمانده را رد میکند. جستجوی دودویی دقیقاً همین کار را روی یک لیست مرتب انجام میدهد:
پایتون def binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1
با یک میلیارد آیتم مرتبشده، به حدود ۳۰ مقایسه نیاز دارد، در حالی که بررسی تکتک آنها میتواند کل یک میلیارد را انجام دهد، و من همیشه این موضوع را خندهدار میدانم.
O(n) و O(n log n)
یک الگوریتم خطی هر عنصر را به تعداد ثابتی بازدید میکند، همانطور که اگر بخواهید بزرگترین عدد را در یک ستون صفحه گسترده به صورت چشمی پیدا کنید، این کار را انجام میدهید. O(n log n) مبنای مرتبسازی مناسب است. مرتبسازی ادغامی، لیست را به آیتمهای تکی تقسیم میکند (log n سطح تقسیم) و سپس در حین ادغام، یک گذر خطی در هر سطح انجام میدهد، بنابراین زمان اجرای آن ثابت میماند، چه دادهها مرتب شده باشند و چه بهم ریخته.
O(n²) و بدتر
کد درجه دوم تقریباً همیشه یک حلقه دارد که درون حلقه دیگری قرار گرفته است، مانند این بررسی تکراری که هر جفت را مقایسه میکند:
پایتون def has_duplicate(items): برای i در محدوده (len(items)): برای j در محدوده (i + 1، len(items)): اگر items[i] == items[j]: مقدار True را برمیگرداند مقدار False را برمیگرداند
رشد نمایی و فاکتوریل به مراتب بدتر هستند. فیبوناچی بازگشتی کتاب درسی، زیرمسئلههای یکسانی را بارها و بارها حل میکند، بنابراین هر +۱ روی n تقریباً کار را دو برابر میکند. در n = ۲۰ متوجه نخواهید شد؛ در n = ۶۰ میتوانید شام بپزید، آن را بخورید، بشویید، و هنوز هم انجام نشده است.
نحوه محاسبه گام به گام پیچیدگی زمانی
تقریباً هیچوقت برای محاسبهی پیچیدگی زمانی به اثبات رسمی نیاز ندارید. من این لیست را در ذهنم مرور میکنم و بیشتر کدهایی که میبینم را پوشش میدهد:
- n را تعریف کنید. اندازه ورودی را تعیین کنید: طول یک لیست، تعداد گرهها در یک گراف، تعداد ارقام در یک عدد.
- کار را در هر سطر بشمارید. دستورات ساده (انتسابها، مقایسهها، محاسبات) هزینهای معادل O(1) دارند.
- بلوکهای متوالی را اضافه کنید. دو حلقه یکی پس از دیگری، هر کدام روی n، داریم n + n = 2n.
- بلوکهای تو در تو را ضرب کنید. یک حلقه روی n داخل حلقه دیگری روی n، نتیجه n × n = n² را میدهد.
- ثابتها را حذف کنید. 2n تبدیل به n و 500 تبدیل به 1 میشود.
- فقط جمله غالب را نگه دارید. در n² + n، با افزایش n، بخش n² بقیه را کوچک جلوه میدهد.
یکی از آنها را سریع حل کردم. حاصل شمارش شما میشود T(n) = 3n² + 5n + 2. یک میلیون را در نظر بگیرید: 3n² برابر با سه تریلیون و 5n برابر با پنج میلیون است. خطای گرد کردن. آن را O(n²) بنامید، تمام.
حلقههایی که به جای اینکه یکییکی اجرا شوند، از جایی به جای دیگر میپرند، زیرکانهتر هستند:
پایتون def count_halvings(n): steps = 0 while n > 1: n //= 2 steps += 1 return steps
هر دور n را به نصف کاهش میدهد، بنابراین این حلقه while پس از تقریباً log₂(n) دور، متوقف میشود. که اساساً کل پاسخ به این سوال است که "پیچیدگی زمانی چه زمانی O(log n) است؟" اگر آنچه باقی میماند در هر مرحله با ضریب ثابتی کاهش یابد، شما به هدف خود رسیدهاید.
بازگشتی به یک ابزار دیگر، یعنی بازگشتی، نیاز دارد. مرتبسازی ادغامی دو کار نصف اندازه و سپس یک ادغام انجام میدهد، بنابراین T(n) = 2T(n/2) + n. قضیه اصلی، یک برگه تقلب برای بازگشتیهای آن شکل است و برای این مورد، O(n log n) را تولید میکند.
و یک قانون کلی از برنامهنویسی رقابتی که خیلی به آن تکیه میکنم: یک ماشین معمولی چیزی حدود ۱۰⁸ عملیات ساده را در ثانیه انجام میدهد. خیلی تقریبی است، اما برای بررسی دقیق پیچیدگی زمانی یک راهحل قبل از ارسال کافی است. با n در ۱۰⁵، O(n²) حدود ۱۰¹⁰ عملیات است، بنابراین زمان شما تمام میشود. O(n log n) کمتر از ۲ میلیون است. به راحتی اجرا میشود.
تحلیل بدترین حالت، بهترین حالت و حالت میانگین
اگر به یک الگوریتم ورودیهای متفاوتی بدهیم، حجم کار میتواند به شدت تغییر کند. جستجوی خطی این را به خوبی نشان میدهد:
- بهترین حالت: چیزی که شما میخواهید این است که درست در جلو قرار بگیرد. یک مقایسه کافی است و تمام.
- بدترین حالت: یا در انتهاست، یا اصلاً وجود ندارد. این n مقایسه است.
- حالت میانگین: اگر میتوانست هر جایی با شانس برابر باشد، به طور میانگین حدود n/2 را بررسی میکنید. البته، باز هم O(n) است.
از یک توسعهدهنده در مورد «پیچیدگی» چیزی بپرسید، تقریباً همیشه بدترین حالت پیچیدگی زمانی را به شما میدهد، زیرا این عدد، وعدهای است که میتوانید بر اساس آن برنامهریزی کنید.
فرض کنید API شما در بدترین حالت یک درخواست را با سرعت O(n) مدیریت میکند. عالی است، حالا میدانید که کندترین درخواست چگونه رفتار میکند، و همچنین وقتی کسی عمداً اطلاعات بیارزش برای شما ارسال میکند، تحت پوشش هستید. مردم کاملاً این کار را میکنند: اگر یک مهاجم بفهمد کدام کلیدها باعث برخورد جدول هش شما میشوند، آنها تنها کلیدهایی هستند که برای مدتی خواهید دید.
وقتی سناریوی بد به ندرت پیش میآید، حالت متوسط ارزش بررسی دارد. مرتبسازی سریع در اینجا نمونه بارز است، که میانگین آن O(n log n) است، اما اگر به طور سادهلوحانه روی دادههایی که از قبل مرتب شدهاند، محورهایی را انتخاب کنید، به O(n²) میلغزد. کتابخانههای استاندارد با محورهای تصادفی یا با تغییر به یک الگوریتم مرتبسازی متفاوت، زمانی که بازگشت به طرز مشکوکی عمیق میشود، این مشکل را حل میکنند.
پیچیدگی فضایی و فضای کمکی چیست؟
حافظه، صورتحساب دیگری است که یک الگوریتم اجرا میکند. پیچیدگی فضا، میزان حافظه مورد نیاز با افزایش اندازه ورودی را پیگیری میکند و شما آن را با همان نماد O بزرگ به عنوان زمان مینویسید.
بخشی از آن حافظه، خود ورودی است که صرف نظر از اینکه با آن چه میکنید، هزینه آن را میپردازید. بخشی که در واقع کنترل میکنید، فضای کمکی نامیده میشود، به معنی چیزهای اضافی که کد شما هنگام کار به آن اختصاص میدهد، مانند متغیرهای موقت و آرایههای جدید، به علاوه پشته فراخوانی که هیچ کس تا زمانی که به آن دسترسی پیدا نکند، آن را به خاطر نمیآورد.
چند مورد سریع:
- جابجایی دو متغیر صرف نظر از هر چیز دیگری به چند جایگاه نیاز دارد، بنابراین فضای کمکی O(1) است.
- کپی کردن لیستی از n آیتم به یک لیست جدید، O(n) حافظه اضافی برای شما به همراه دارد.
- با بازگشت به n سطح عمیق، n فریم روی پشته باقی میماند که فضای O(n) را اشغال میکند، حتی اگر هرگز آرایهای نساخته باشید.
من یک توسعهدهنده تازهکار را دیدم که یک بعدازظهر را به آن نفر آخر باخت. تابع بازگشتی آنها طوری به نظر میرسید که انگار اصلاً از حافظه استفاده نمیکند، اما هر فراخوانی ناتمام روی پشته پارک میشد و منتظر بازگشت فراخوانیهای عمیقتر میماند و با یک ورودی بزرگ، کل ماجرا با سرریز پشته از بین میرفت.
بسیاری از بهینهسازیها صرفاً مبادله حافظه با زمان یا برعکس است. Memoization نتایجی را که قبلاً محاسبه کردهاید، ذخیره میکند که فیبوناچی ساده را از O(2ⁿ) تا O(n) زمان در ازای O(n) حافظه کاهش میدهد. جداول هش با صرف فضا برای باکتها، میانگین جستجوهای O(1) را برای شما میخرند. در سروری با 64 گیگابایت رم، این مبادله معمولاً بدیهی است، اما در یک میکروکنترلر یا درون یک قرارداد هوشمند، باید دوباره فکر کنید.

پیچیدگی زمانی و مکانی ساختارهای داده رایج
انتخاب ساختار داده مناسب معمولاً بهتر از تنظیم جزئی هر چیزی است که درون حلقه شما قرار دارد. هزینههای متوسط برای مواردی که بیشتر به آنها خواهید رسید:
| ساختار داده | دسترسی | جستجو | درج | حذف | فضا |
|---|---|---|---|---|---|
| آرایه | اُ(1) | O(n) | O(n) | O(n) | O(n) |
| لیست پیوندی | O(n) | O(n) | O(1) | اُ(1) | O(n) |
| جدول هش | ناموجود | O(1) | اُ(1) | اُ(1) | O(n) |
| درخت جستجوی دودویی متوازن | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| هیپ دودویی | O(1) برای حداقل/حداکثر | O(n) | O(log n) | O(log n) | O(n) |
دو پاورقی. درج و حذف لیست پیوندی فقط در صورتی O(1) است که از قبل گره را در اختیار داشته باشید. و یک جدول هش میتواند در صورت برخورد تعداد زیادی کلید به O(n) کاهش یابد.
الگوریتمهای مرتبسازی نیز به همان اندازه متفاوت هستند:
| الگوریتم مرتبسازی | بهترین | میانگین | بدترین | فضای کمکی |
|---|---|---|---|---|
| مرتبسازی حبابی | O(n) | O(n²) | O(n²) | اُ(1) |
| مرتبسازی ادغامی | O(n log n) | O(n log n) | O(n log n) | O(n) |
| مرتبسازی سریع | O(n log n) | O(n log n) | O(n²) | O(log n) |
| مرتبسازی هیپ | O(n log n) | O(n log n) | O(n log n) | اُ(1) |
مرتبسازی ادغامی قابل پیشبینی است اما به حافظه اضافی نیاز دارد. مرتبسازی هیپ مرتبسازی را درجا انجام میدهد و همان بدترین حالت را حفظ میکند. مرتبسازی سریع، با وجود سقف زشتتر، در عمل تمایل به پیروزی دارد.
پیچیدگی زمانی در بلاکچین و قراردادهای هوشمند
اینجاست که ماجرا جالب میشود. روی سرور خودتان، یک الگوریتم نامرتب، CPU را هدر میدهد و شاید کاربر را اذیت کند. روی اتریوم یا هر زنجیره EVM دیگری، پول را هدر میدهد. هر کد عملیاتی که یک قرارداد هوشمند اجرا میکند، هزینهای دارد که با کوین بومی زنجیره پرداخت میشود، بنابراین تعداد عملیات شما به صورت یک خط در صورتحساب کسی نمایش داده میشود. به عبارت دیگر، پیچیدگی زمانی بد، برچسب قیمت دارد.
فرض کنید قراردادی دارید که برای پرداخت پاداش، هر دارنده توکن را در یک چرخه قرار میدهد. O(n) و با هر دارنده جدید، گس (gas) به آرامی افزایش مییابد. در روز راهاندازی، هیچکس متوجه نمیشود.
سپس فهرست دارندگان همچنان در حال افزایش است. یک روز پرداخت به سوخت بیشتری نسبت به محدودیت سوخت بلوک نیاز دارد، که سقف میزان سوختی است که یک بلوک میتواند در آن جای گیرد. پس از آن تراکنش نمیتواند انجام شود. نه اینکه "کند است". هرگز موفق نمیشود و هر مبلغی که پشت آن تابع منتظر بوده، اساساً گیر میکند. حسابرسان حلقههای نامحدودی مانند این را تحت عنوان انکار سرویس ثبت میکنند و این کاملاً منصفانه است.
راهحلها، تفکر پیچیدگی هستند، به زبان ساده:
- کار را به دستههایی با اندازه ثابت در طول چندین تراکنش تقسیم کنید.
- قضیه را برعکس کنید تا هر کاربر پاداش خودش را مطالبه کند. هر فراخوانی O(1) است.
- حلقه را با یک اثبات مرکل عوض کنید.
من عاشق اثباتهای مرکل هستم، به عنوان مثالی از اینکه چرا log n اینقدر در زنجیره اهمیت دارد. یک درخت مرکل، حجم زیادی از دادهها را در یک هش ریشه هش میکند.
برای اثبات تعلق یک ورودی به مجموعهای از n، به حدود log₂(n) هش نیاز دارید. برای یک میلیون ورودی، این تقریباً 20 میشود. نه یک میلیون. ایردراپها به این متکی هستند و کیف پولهای سبک بیتکوین از همین ترفند برای تأیید تراکنش بدون دانلود کل بلوک استفاده میکنند.
خارج از زنجیره، همان معامله. یک بکاند پرداخت را تصور کنید که هر تراکنش بلاکچین ورودی را با اسکن هر فاکتور باز، با یک فاکتور مطابقت میدهد. O(n) برای هر پرداخت، و با رشد فروشگاه کندتر میشود. فاکتورها را در یک نقشه هش که توسط آدرس یا شناسه کلیدگذاری شده است قرار دهید و هر تطابق O(1) است. و اگر ترجیح میدهید خودتان آن لولهکشی را نسازید و از آن مراقبت نکنید، یک درگاه پرداخت کریپتو مانند Plisio این کار را برای شما انجام میدهد.