نماد Big-O و تحلیل پیچیدگیBig-O & Complexity Analysis

بیا صادق باشیم: بیشتر ما «Big-O» را مثل یک وردِ جادویی حفظ کرده‌ایم — «HashMap برابر O(1)»، «مرتب‌سازی برابر O(n log n)» — بدون اینکه واقعاً حس کنیم زیرش چه می‌گذرد. در این درس می‌خواهیم آن حسِ درونی را بسازیم. قرار است هر واژه را از صفر باز کنیم تا وقتی سرِ مصاحبه می‌نشینی، نه فقط جواب درست را بدهی، بلکه بدانی چرا درست است.

بخش ۰ — واژه‌هایی که اول باید بشناسی

قبل از هر چیز، سه واژه‌ی پایه که در کل درس تکرار می‌شوند:

• ورودی n: اندازه‌ی چیزی که به الگوریتم می‌دهی. طول یک لیست، تعداد کاربران، تعداد کاراکترهای یک رشته. n قهرمان همه‌ی داستان‌های ماست.
• مجانبی (asymptotic): صفتی که یعنی «وقتی n به سمت بی‌نهایت می‌رود». تصور کن با یک دوربین از خیلی دور به نمودار رشدِ الگوریتم نگاه می‌کنی؛ جزئیاتِ نزدیک محو می‌شوند و فقط شکل کلی رشد می‌ماند. Big-O همان نگاهِ از دور است.
• ضریب ثابت (constant factor): عددی که به رشد نمی‌چسبد. اگر الگوریتمی 5n عملیات کند و دیگری 100n، هر دو «خطی» (O(n)) هستند؛ آن ۵ و ۱۰۰ ضریب ثابت‌اند و Big-O عمداً آن‌ها را نادیده می‌گیرد.

Big-O دقیقاً چه چیزی را می‌سنجد

اولین سوءتفاهمِ همه این است که فکر می‌کنند Big-O یک کرنومتر است که می‌گوید «این کد ۲ میلی‌ثانیه طول می‌کشد». نه. Big-O می‌سنجد که هزینه‌ی منابع یک الگوریتم چگونه با بزرگ‌شدن ورودی n به سمت بی‌نهایت رشد می‌کند، و ضرایب ثابت و جملات مرتبه‌پایین را نادیده می‌گیرد.

آن «منبع» معمولاً زمان است (تعداد عملیات پایه) یا فضا (حافظه‌ی اضافی)، اما می‌تواند هر چیزی باشد: فراخوانی‌های I/O، رفت‌وبرگشت شبکه (network round-trips)، تعداد مقایسه‌ها، یا حتی cache miss (وقتی داده‌ای که CPU می‌خواهد در حافظه‌ی نزدیکِ سریع نیست و باید از حافظه‌ی دور و کند بیاید).

مهم‌ترین جمله‌ای که باید در ذهنت حک شود:

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

هزینه
 ^                                   O(2^n)   O(n^2)
 |                                  /        /
 |                                 /       /
 |                               /      /      O(n log n)
 |                             /     /     /
 |                           /    /    /        O(n)
 |                         /   /   /  ______/
 |                       / / /____/______________ O(log n)
 |                     //_/_______________________ O(1)
 +----------------------------------------------------> n

ببین چطور O(2^n) و O(n²) مثل موشک بالا می‌روند، در حالی که O(log n) و O(1) تقریباً صاف می‌مانند. این تصویر را حفظ کن؛ شهودِ کل فصل در همین است.

و این ترتیب کلاس‌های رایج، از بهترین (کندترین رشد) به بدترین (تندترین رشد):

O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

سه نماد: O و Θ و Ω

همه به‌طور محاوره‌ای می‌گویند «Big-O»، اما در واقع سه کرانِ متمایز وجود دارد. دانستنِ فرقشان یک سیگنالِ سطح‌ارشد است.

حالا نسخه‌ی دقیق و ریاضی، که ترسناک به‌نظر می‌رسد ولی ساده است. به‌طور صوری، g(n) = O(f(n)) اگر و تنها اگر ثابت‌های c > 0 و n₀ وجود داشته باشند به‌طوری‌که برای همه‌ی n ≥ n₀ داشته باشیم g(n) ≤ c·f(n). یعنی: «از یک جایی به بعد (n₀)، اگر f را در یک عددِ ثابت ضرب کنم، همیشه بالای g می‌ماند.» برای Θ باید g بین دو کران محصور (sandwiched) شود: c₁·f(n) ≤ g(n) ≤ c₂·f(n).

یک ظرافتِ آخر که خیلی‌ها قاطی می‌کنند: O، Θ، Ω درباره‌ی رشد هستند و کاملاً مستقل (عمود) از مفهومِ بهترین/میانگین/بدترین حالت (case). یعنی می‌توانی پیچیدگیِ بدترین‌حالت را هم تنگ (Θ) و هم شل (O) بیان کنی. گفتن «QuickSort برابر O(n log n) است» بی‌دقت است چون بدترین حالتش Θ(n²) است؛ اما «QuickSort در بدترین حالت O(n²) و در حالت میانگین Θ(n log n) است» دقیق و حرفه‌ای است.

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

«حالت» یعنی کدام ورودی را داری اندازه می‌گیری. سه تا مهم‌اند:

• بدترین حالت (worst case): ورودی‌ای که هزینه را بیشینه می‌کند. این چیزی است که SLA (تعهدِ سطح سرویس) را حولش طراحی می‌کنی، چون کرانِ tail latency (تأخیرِ بدترین درصدِ درخواست‌ها) را می‌دهد. get در HashMap در بدترین حالت O(n) است اگر همه‌ی کلیدها در یک bucket برخورد (collision) کنند.
• میانگین حالت (average case): هزینه‌ی موردانتظار روی یک توزیع از ورودی‌ها. get در HashMap به‌طور میانگین O(1) است. QuickSort به‌طور میانگین Θ(n log n) است.
• بهترین حالت (best case): خوش‌شانس‌ترین ورودی. مرتب‌سازی درجی (insertion sort) روی داده‌ی از قبل مرتب برابر O(n) است. به‌ندرت برای برنامه‌ریزی مفید است، اما گاهی برای بهینه‌سازی به کار می‌آید (خروجِ زودهنگام / early-exit).

تحلیل سرشکن: چرا ArrayList.add برابر O(1) است

اینجا یک معماست. پشتِ ArrayList یک آرایه‌ی ساده قرار دارد. وقتی آرایه پر می‌شود، add مجبور است یک آرایه‌ی بزرگ‌تر تخصیص دهد و همه‌ی عناصر را کپی کند — که آشکارا یک عملیاتِ O(n) است. پس چطور جرأت می‌کنیم بگوییم add برابر O(1) است؟

چرا این پخش‌کردن جواب می‌دهد؟ چون resizeهای گران نادر هستند و هرچه پیش می‌رود نادرتر می‌شوند. ArrayList با ضریبِ حدوداً ۱٫۵ رشد می‌کند — در کدِ JDK دقیقاً newCap = oldCap + (oldCap >> 1) (یعنی ظرفیت قدیم به‌علاوه‌ی نصفش). این رشدِ ضربی یعنی برای رسیدن به اندازه‌ی n فقط حدود log(n) بار resize می‌کنی، و کلِ کارِ کپی در همه‌ی resizeها یک سریِ هندسی (geometric) است که به O(n) جمع می‌شود، نه O(n²).

بیایید عددی ببینیم. فرض کن آرایه دوبرابر می‌شود (ظرفیت‌های ۱، ۲، ۴، ۸، ...):

append در آرایه‌ی دوبرابرشونده (ظرفیت‌های ۱،۲،۴،۸...):
کپی‌ها به‌ازای هر resize:  1  1  2  4  8 ... n/2
مجموع کپی‌ها = 1 + 2 + 4 + ... + n/2  <  n   (هندسی)
=> کل کار برای n درج = O(n)  =>  هر add برابر O(1) سرشکن

جادوی سریِ هندسی این است که 1 + 2 + 4 + ... + n/2 همیشه کمتر از n می‌شود، نه بیشتر. پس کلِ هزینه‌ی n بار append برابر O(n) است. تقسیم بر n عملیات → O(1) سرشکن به‌ازای هر add. هر add منفرد ممکن است O(n) باشد، اما هیچ دنباله‌ای از n بار add نمی‌تواند رویِ‌هم بیش از O(n) هزینه داشته باشد.

ابزارِ صوریِ این استدلال روش حسابداری (accounting method) (یا روش پتانسیل) است: به عملیاتِ ارزان بیش‌ازحد شارژ می‌کنی تا «اعتبار» بانک کنی که بعداً هزینه‌ی عملیاتِ گرانِ نادر را بپردازد. هر add ارزان ۱ واحد برای خودش می‌پردازد به‌علاوه‌ی حدود ۲ واحد اعتبار؛ وقتی resize رخ می‌دهد، اعتبارِ بانک‌شده کپی‌ها را پوشش می‌دهد. مثلِ همان آبگرمکن: هر ماه کمی پول کنار می‌گذاری تا روزِ خرابی، صندوق آماده باشد.

همین منطقِ سرشکن زیربنای HashMap است (put سرشکنِ O(1)، که هنگام resize، rehash می‌کند)، و همین‌طور StringBuilder و ArrayDeque.

// ضدالگو: اگر لیست خیلی بزرگ شود، resize‌های مکرر را مجبور می‌کند.
List<Integer> a = new ArrayList<>();          // خالی شروع می‌شود، در صورت نیاز رشد می‌کند
for (int i = 0; i < 1_000_000; i++) a.add(i); // در کل ~O(n) سرشکن، ~۲۰ بار resize

// بهتر وقتی اندازه معلوم است: صفر resize، یک تخصیص.
List<Integer> b = new ArrayList<>(1_000_000);
for (int i = 0; i < 1_000_000; i++) b.add(i);

بازگشتی‌ها و قضیه‌ی اصلی (Master theorem)

الگوریتم‌های بازگشتی و تقسیم‌وحل (divide-and-conquer) یک نوع معادله‌ی خاص تولید می‌کنند به‌نام بازگشتی (recurrence) — که هزینه‌ی اندازه‌ی n را بر حسبِ هزینه‌ی زیرمسئله‌های کوچک‌تر بیان می‌کند:

T(n) = a·T(n/b) + f(n)

که در آن a = تعداد زیرمسئله‌ها، b = ضریبی که مسئله با آن کوچک می‌شود، و f(n) = کارِ لازم برای تقسیم و ترکیب.

قضیه‌ی اصلی کارِ برگ‌ها (n^(log_b a)) را با f(n) مقایسه می‌کند. فرض کن c = log_b(a) (این «کارِ برگ‌ها» است).

(آن ε یک عددِ مثبتِ کوچک است؛ صرفاً یعنی «به‌طورِ چندجمله‌ای کوچک‌تر/بزرگ‌تر».) حالا چهار مثالِ حل‌شده که باید فوری بشناسی:

• مرتب‌سازی ادغامی (merge sort): T(n) = 2T(n/2) + O(n). اینجا a=2, b=2, c=log₂2=1، و f(n)=n=Θ(n¹) → حالت ۲ → Θ(n log n). هر سطح O(n) کارِ ادغام انجام می‌دهد؛ و log n سطح وجود دارد.
• جست‌وجوی دودویی (binary search): T(n) = T(n/2) + O(1). a=1, b=2, c=0، f=Θ(1)=Θ(n⁰) → حالت ۲ → Θ(log n).
• پیمایش بازگشتی که به دو نیم می‌شود با ترکیبِ ثابت: T(n)=2T(n/2)+O(1). c=1، f=O(n^(1-ε)) → حالت ۱ → Θ(n) (مثلاً شمارشِ اندازه‌ی یک درخت).
• ضربِ کاراتسوبا (Karatsuba): T(n)=3T(n/2)+O(n). c=log₂3≈۱٫۵۸۵، f=O(n^(c-ε)) → حالت ۱ → Θ(n^1.585).

پیچیدگیِ عملیاتِ رایجِ JDK

این جدول را حفظ کن — مصاحبه‌کننده‌ها مستقیم آن را می‌پرسند و تصمیماتِ طراحیِ واقعی را هدایت می‌کند.

حالا ظرافت‌های کلیدی که یک ارشد باید بداند، یکی‌یکی:

• PriorityQueue.remove(Object) و contains برابر O(n) هستند — چون یک هرم فقط در مسیرهای ریشه‌به‌برگ مرتب است، نه سراسری. پس یافتنِ یک عنصرِ دلخواه یعنی پویشِ خطیِ کلِ آرایه. یک «decrease-key» ساده‌لوحانه روی آن نساز.
• TreeMap در ازای کندی، ترتیب می‌خرد — firstKey، floorKey، ceilingKey، headMap، subMap، و پویشِ بازه‌ای، همه O(log n). اگر به پرس‌وجوی بازه‌ای یا پیمایشِ مرتب نیاز داری، این تبادلِ O(log n) در برابرِ O(1) ارزشش را دارد. HashMap هیچ ترتیبی به تو نمی‌دهد.
• هزینه‌ی Stream/پیمایش: پیمایشِ هرکدام O(n) است، اما ترتیبِ پیمایشِ HashMap نامشخص است و هزینه‌اش متناسب با ظرفیت (capacity) است، نه اندازه — یک map بزرگ و عمدتاً خالی، کند پیمایش می‌شود.

تخمینِ پیچیدگی در مصاحبه

اینجا یک رویه‌ی تکرارپذیر که می‌توانی مثلِ یک چک‌لیست دنبال کنی:

۱. متغیرهای اندازه را مشخص کن — اغلب بیش از یکی وجود دارد (n = طولِ لیست، m = تعدادِ پرس‌وجو، k = اندازه‌ی الفبا/انشعاب). با همه‌شان پاسخ بده: O(n·m)، نه یک حرفِ تنها. ۲. حلقه‌های تودرتو ضرب می‌شوند؛ حلقه‌های متوالی جمع می‌شوند. دو پیمایشِ مستقلِ پشتِ‌سرِ‌هم = O(n) + O(n) = O(n). حلقه‌ی داخلِ حلقه روی همان n = O(n²). ۳. مراقبِ حلقه‌هایی باش که n بار اجرا نمی‌شوند. for (i=1; i<n; i*=2) فقط log n بار اجرا می‌شود، چون i هر بار دوبرابر می‌شود. هر حلقه‌ای که شمارنده‌اش نصف یا دوبرابر شود، لگاریتمی است. ۴. بازگشت → بازگشتی → قضیه‌ی اصلی (یا درخت را بشمار). ۵. کارِ پنهانِ درونِ بدنه‌ی حلقه را حساب کن — یک .contains() روی لیست، یک substring، یک sort، یک rehash. بیشترِ پاسخ‌های اشتباه دقیقاً از اینجا می‌آید (دام‌ها را پایین ببین). ۶. در پایان ثابت‌ها و جملاتِ غیرغالب را حذف کن: O(3n² + 5n + 100) → O(n²).

دام‌های رایج و هزینه‌های پنهان

اینجا محلی است که مهندسانِ باتجربه هم می‌لغزند. تقریباً همه‌ی این دام‌ها یک شکلِ واحد دارند: یک عملیاتِ گرانِ پنهان درونِ یک حلقه.

۱. الحاقِ رشته در حلقه → O(n²)

رشته‌ها در جاوا تغییرناپذیر (immutable) هستند — یعنی نمی‌شود تغییرشان داد، فقط می‌شود یک رشته‌ی جدید ساخت. پس s += x در هر تکرار یک رشته‌ی کاملاً جدید می‌سازد و همه‌ی کاراکترهای قبلی را کپی می‌کند. n بار الحاق روی رشته‌های در حالِ رشد برابرِ 1+2+...+n = O(n²) کپیِ کاراکتر است.

// O(n^2): هر += کل رشته‌ی انباشته را کپی می‌کند.
String s = "";
for (int i = 0; i < n; i++) s += i;   // درجه دو — دام کلاسیک مصاحبه

// O(n): StringBuilder یک char[] قابل‌تغییر resize‌شونده را ویرایش می‌کند (append سرشکن O(1)).
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append(i);
String result = sb.toString();

۲. list.contains() درونِ حلقه → O(n²)

// O(n*m): contains() روی List برابر O(n)، m بار صدا زده می‌شود.
List<Integer> seen = new ArrayList<>();
for (int x : data) {
    if (!seen.contains(x)) seen.add(x);   // پویش O(n) در هر تکرار
}

// O(n): HashSet.contains به‌طور میانگین O(1).
Set<Integer> seen = new HashSet<>();
for (int x : data) seen.add(x);   // حذف تکراری در زمان خطی

می‌بینی؟ همان contains که روی ArrayList برابرِ O(n) بود، روی HashSet می‌شود O(1) میانگین، و کلِ کار از O(n²) به O(n) سقوط می‌کند. این تنها با عوض‌کردنِ نوعِ کالکشن.

۳. سربارِ autoboxing و تخصیصِ پنهان

Autoboxing یعنی تبدیلِ خودکارِ یک int (نوعِ پایه) به یک Integer (شیء). HashMap<Integer,Integer>، List<Long>، و boxing در stream — هر تبدیلِ int↔Integer یک تخصیصِ حافظه می‌کند (خارج از کشِ -128..127 که جاوا اعدادِ کوچک را در آن نگه می‌دارد) و غیرمستقیم‌سازیِ اشاره‌گر و فشارِ GC می‌افزاید. این Big-O را تغییر نمی‌دهد، اما می‌تواند ضریبِ ثابت را ۵ تا ۱۰ برابر کند و در حلقه‌های تنگ کلِ زمانِ اجرا را ببلعد.

// boxing پنهان: sum از نوع Long است، هر += آن را unbox می‌کند، جمع، دوباره box -> تخصیص‌ها.
Long sum = 0L;
for (long v : values) sum += v;   // میلیون‌ها تخصیص Long

// اصلاح‌شده: انباشتگر primitive، صفر boxing.
long total = 0L;
for (long v : values) total += v;

فقط تفاوتِ Long (بزرگ، شیء) با long (کوچک، پایه) کلِ ماجراست. موردِ ظریف‌تر: boxing در مسیرِ داغِ کلیدِ map عملکردِ HashMap را کاهش می‌دهد؛ و map.get(intVar) در هر فراخوانی autobox می‌کند. برای کارِ سنگین با primitive، کالکشن‌های تخصصیِ primitive (مثلِ Eclipse Collections یا fastutil) را در نظر بگیر که هم حافظه و هم ضریبِ ثابت را کم می‌کنند.

۴. الحاقِ کالکشن‌ها / بازسازیِ immutableها در حلقه

// O(n^2): هر concat لیست در حال رشد را کپی می‌کند.
List<Integer> acc = List.of();
for (int x : data) acc = concat(acc, List.of(x));  // هر بار کل تاکنون را کپی می‌کند

این دقیقاً همان شکلِ الحاقِ رشته است. هر «کلِ چیز را کپی کن تا یکی اضافه شود» درونِ حلقه، درجه‌دو است.

۵. O(n) پنهان در List.remove و shift

ArrayList.remove(i) همه‌ی عناصرِ بعدی را یک خانه به عقب shift می‌کند: O(n). حذف در یک حلقه‌ی رو به جلو حینِ پیمایش برابرِ O(n²) و اغلب باگ‌دار است. حذفِ مکرر از ابتدای لیست هم O(n²) است — برای این کار از ArrayDeque استفاده کن.

۶. مرتب‌سازی درونِ حلقه، یا مرتب‌سازیِ مجدد

یک sort با O(n log n) که درونِ یک حلقه‌ی O(n) قرار گیرد، در کل O(n² log n) می‌شود. اگر داده تغییر نمی‌کند، یک بار بیرون از حلقه sort کن.

۷. substring و regex

String.substring برابرِ O(k) است (که k طولِ زیررشته است) — از Java 7u6 به بعد کپی می‌کند و دیگر آرایه‌ی پشتی را به اشتراک نمی‌گذارد. پس یک حلقه که substring می‌گیرد می‌تواند O(n²) را پنهان کند. و عقب‌گردِ regex (backtracking) می‌تواند روی الگوهای بیمارگونه نمایی شود — پدیده‌ای به‌نامِ catastrophic backtracking که می‌تواند یک سرور را با یک ورودیِ کوچک قفل کند.

۸. .collect در Stream و ساختارهای میانی

Stream رفتارِ مجانبی را تغییر نمی‌دهد، اما .sorted()، .distinct() (که به یک HashSet نیاز دارد) و .collect(toList())ِ زنجیره‌ای هرکدام تخصیصِ حافظه می‌کنند. یک .sorted() در stream برابرِ O(n log n) است حتی اگر فقط عنصرِ اول را بگیری — در این حالت به‌جایش از رویکردِ جزئی یا min() استفاده کن.

پیچیدگیِ فضا (space complexity)

همان نماد، اما این بار روی حافظه‌ی اضافی فراتر از ورودی اعمال می‌شود.

جدول‌های حافظه‌سازی/DP (dynamic programming) برابرِ O(states) هستند (تعدادِ حالت‌هایی که ذخیره می‌کنی). یک الگوریتمِ درجا (in-place) برابرِ O(1) فضای کمکی است. مصاحبه‌کننده‌ها بیشتر و بیشتر می‌پرسند «می‌توانی در O(1) فضا انجامش دهی؟» — که معمولاً نشانه‌ای است برای استفاده از دو اشاره‌گر (two pointers)، جابه‌جاییِ درجا، یا استفاده از خودِ آرایه‌ی ورودی به‌عنوانِ دفترچه‌ی موقت.

مراقبِ تبادلِ زمان-فضا (time–space tradeoff) باش: یک HashSet برای حذفِ تکراریِ O(1) برابرِ O(n) حافظه هزینه دارد؛ ترفندِ دو اشاره‌گر روی داده‌ی مرتب O(1) فضاست اما ابتدا به O(n log n) زمان برای sort نیاز دارد. هیچ ناهارِ مجانی وجود ندارد.

بهترین شیوه‌ها (خلاصه‌ی عملی)

• تنگ‌ترین کران را بیان کن و همیشه کدام حالت و کدام منبع را نام ببر (Θ(n) زمان، O(1) فضا، بدترین حالت).
• وقتی ورودی‌ها مستقل‌اند از چند متغیر استفاده کن — فروپاشیدنِ O(V+E) به O(n) برای گراف‌ها غلط است.
• کالکشن‌ها را از پیش اندازه‌بندی کن (new HashMap<>(expected/0.75 + 1)، new ArrayList<>(n)) تا resizeهای سرشکن را از بین ببری.
• ArrayDeque را به Stack/LinkedList ترجیح بده؛ به‌طور پیش‌فرض ArrayList را به LinkedList ترجیح بده.
• وقتی حلقه‌ای می‌بینی، فوراً بپرس «هزینه‌ی بدنه چقدر است؟» — contains/substring/sortِ پنهان جایی است که درجه‌دوها مخفی می‌شوند.
• قبل از اصلاحِ کلاسِ مجانبی، ثابت‌ها را ریزبهینه نکن؛ اما وقتی کلاس درست شد، ثابت‌ها را هم نادیده نگیر — محلیتِ کش و boxing واقعی‌اند.

سوالات مصاحبه

String s = "";
for (int i = 0; i < 5; i++) s += i;
System.out.println(s + " len=" + s.length());

List<Integer> result = new ArrayList<>();
for (int x : input)                    // n تکرار
    if (!result.contains(x)) result.add(x);   // هر بار O(n)

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++) work();