Big-O والـ Complexitytime & space complexity · growth rates · hidden costs in JavaScript
قبل ما تكتب الحل، تقدر تعرف هياخد TLE ولا لأ. Big-O بيعدّ الحل بيعمل كام خطوة، وبيشوف العدد ده بيكبر إزاي لما الـ input يكبر، من غير ما تشغّل حاجة.
هتطلع من الفصل ده وإنت عارف
- Big-O بيقيس إيه بالظبط، وليه بنشيل الثوابت والحدود الصغيرة.
- تحسب الـ complexity لأي كود: loops ورا بعض، جوه بعض، بتنص، بتعتمد على بعض، و recursion.
- تحوّل سطر الـ constraints لـ complexity مسموحة بقاعدة الـ 10⁸.
- تحسب الـ space ومنها الـ recursion stack، وتفهم ليه
pushO(1). - تمسك الـ hidden costs في JS اللي بتحوّل O(n) لـ O(n²) أو بتوقّع الكود خالص.
ليه Big-O؟
في الفصل اللي فات قلنا كذا مرة "ده O(n²) يعني TLE". دلوقتي نفهم الجملة دي جاية منين.
تخيّل حلين لنفس المسألة، الاتنين بيطلّعوا الإجابة الصح على مثال المسألة في أقل من ملّي ثانية. تدوس Submit: الأول يعدّي والتاني TLE. ليه؟ لأن المثال فيه 6 أرقام، والـ hidden test فيه 100,000. فالسؤال مش "بياخد قد إيه على 6؟". السؤال: لما الـ input يكبر، الوقت بيكبر بسرعة قد إيه؟
القياس بالساعة بيتغيّر حسب الجهاز واللغة. فبنعدّ حاجة ثابتة: عدد الـ basic operations (مقارنة، جمع، قراية من array) كدالة في حجم الـ input n.
شوف ده على 6 أرقام بس: function بتعدّي على كل عنصر، وواحدة بتعدّي على كل زوج:
| n | single: n | pairs: n(n - 1)/2 | pairs على 10⁸/ثانية |
|---|---|---|---|
| 6 | 6 | 15 | ولا حاجة |
| 1,000 | 1,000 | 499,500 | 5 ملّي ثانية |
| 100,000 | 100,000 | ≈ 5 × 10⁹ | حوالي 50 ثانية: TLE |
Big-O هو اسم "شكل" النمو ده: O(n) و O(n²). ومن غير ما تشغّل حاجة، عرفت إن التانية مش هتعدّي مع n = 10⁵.
طب إمتى تحسبها، وإزاي تحوّل سطر الـ constraints لرقم تحكم بيه؟
إمتى تحسبها، وقاعدة الـ 10⁸
السيرفر بيعمل تقريبًا 10⁸ عملية بسيطة في الثانية، والـ time limit غالبًا ثانية أو اتنين. فالسؤال: الحل مع أكبر n هيعمل كام عملية؟
| لو n لحد | المسموح | عمليات تقريبًا | حلول بتطلع كده |
|---|---|---|---|
| 10 | O(n!) | 3.6 × 10⁶ | كل الـ permutations |
| 20 | O(2ⁿ) | 10⁶ | كل الـ subsets، backtracking |
| 500 | O(n³) | 1.25 × 10⁸ | تلات loops جوه بعض |
| 5,000 | O(n²) | 2.5 × 10⁷ | nested loops، 2D DP |
| 10⁵ | O(n log n) | 1.7 × 10⁶ | sort، heap، binary search لكل عنصر |
| 10⁶ | O(n) | 10⁶ | one pass، hash map، two pointers |
| 10⁹ | O(log n) أو O(√n) | 30 أو 31,623 | binary search، معادلة |
واقراه بالعكس: n <= 20 تلميح إن الحل المتوقع exponential، فما تدوّرش على O(n).
flowchart TD
A["Read the largest n"] --> B{"n up to 20?"}
B -- yes --> X["O(2^n): try all subsets"]
B -- no --> C{"n up to 5000?"}
C -- yes --> Y["O(n^2): nested loops are fine"]
C -- no --> D{"n up to 10^6?"}
D -- yes --> Z["O(n log n) or O(n): sort, hash map, two pointers"]
D -- no --> W["O(log n): binary search or a formula"]
أول سؤال بعد ما تقرا المسألة.
بنقول O(n) و O(n²). بس Big-O بيقيس إيه بالظبط، وليه 3n² + 5n بقت n²؟
Big-O بيقيس إيه بالظبط
بنعدّ العمليات البسيطة: أي حاجة بتاخد وقت ثابت مهما كان n (a + b، x < y، nums[i]). العدد ده دالة في n، مثلًا 3n² + 5n + 20. وبعدين:
- نشيل الحدود الصغيرة:
3n² + 5n + 20→3n². - نشيل الثابت:
3n²→n². فالإجابةO(n²).
| n | 3n² | 5n | 20 | نسبة الـ 3n² من الكل |
|---|---|---|---|---|
| 10 | 300 | 50 | 20 | 81% |
| 1,000 | 3,000,000 | 5,000 | 20 | 99.83% |
| 100,000 | 3 × 10¹⁰ | 500,000 | 20 | 99.998% |
الحدود الصغيرة بتختفي لما n يكبر، وده الوقت الوحيد اللي بيفرق. والثابت بيتغيّر حسب الجهاز وطريقة الكتابة، لكن شكل النمو لأ: لو n اتضاعف، أي O(n²) بيتضرب في 4، سواء الثابت 3 ولا 300.
O(g(n)) معناها: من عند n كبيرة كفاية، عدد العمليات مش هيعدّي c × g(n) لثابت ما c. فيه كمان Θ (النمو بالظبط) و Ω (أرضية)، بس في الانترفيو الناس بتقول O وتقصد النمو بالظبط.
- متغيرين مختلفين بيفضلوا الاتنين. loop على n وبعدين loop على m =
O(n + m). ولو nested =O(n · m)مشO(n²). ما ينفعش تشيل m لأنها ممكن تبقى أكبر بكتير. - الثابت الكبير لسه ثابت. loop بتلف 26 مرة جوه loop على n =
26n=O(n). وInt32Array(26)memoryO(1).
عرفنا بنشيل إيه. يلا نشوف الـ classes المشهورة بالأرقام.
الـ complexity classes المشهورة
| Class | الإحساس | مثال | عمليات على n = 10⁵ | الوقت على 10⁸/ثانية |
|---|---|---|---|---|
| O(1) | بصّة واحدة | arr[i]، push، map.get | 1 | ولا حاجة |
| O(log n) | بتنص المسألة كل خطوة | binary search | 17 | ولا حاجة |
| O(n) | كل عنصر مرة | one pass | 10⁵ | 1 ملّي ثانية |
| O(n log n) | n مرة شغل log n | sort | ≈ 1.7 × 10⁶ | 17 ملّي ثانية |
| O(n²) | كل عنصر مع كل عنصر | nested loops | 10¹⁰ | 100 ثانية: TLE |
| O(2ⁿ) | كل عنصر داخل أو برا | كل الـ subsets | رقم فيه 30,103 خانة | مستحيل |
| O(n!) | كل الترتيبات | كل الـ permutations | رقم فيه 456,574 خانة | مستحيل |
الـ exponential مرفوض على n كبيرة بس. على n صغيرة عادي: 2²⁰ ≈ 10⁶ تمام، و 10! ≈ 3.6 × 10⁶ تمام، لكن 20! ≈ 2.4 × 10¹⁸ مستحيل.
والـ log بيكبر ببطء رهيب: n لازم تتضاعف عشان يزيد 1. log₂(10⁵) ≈ 17، و log₂(10⁹) ≈ 30. والـ base مش بيفرق في Big-O، فبنكتب O(log n).
طب إزاي تعرف الكود بتاعك في أنهي class؟ نبدأ بالـ loops.
إزاي تحسبها من الكود: الـ loops
4 قواعد بتغطي أغلب الكود:
1. ورا بعض: اجمع، وخد الأكبر
2. جوه بعض: اضرب
3. الداخلية بتعتمد على الخارجية: اجمع اللفّات
"الداخلية أقصر، يبقى أحسن"؟ هي نص العدد آه، بس النص ثابت، فلسه O(n²).
4. المتغير بيتضرب أو بيتقسم: log n
لو الـ update بقى i *= 2 أو i = Math.floor(i / 2) بدل i++، عدد اللفّات = عدد مرات القسمة على 2 = log₂ n.
- الفرق كله في الـ update:
Math.floor(i / 2)مشi++. الـfloorعشانiيفضل integer، والـ>= 1عشان لفةi = 1تتحسب، وبعدهاiيبقى 0 فتقف. - شغل ثابت. لو هنا loop على n، الكل يبقى
O(n log n). - النتيجة
⌊log₂ n⌋ + 1: 7 لـ n = 100، و 17 لـ 10⁵، و 30 لـ 10⁹.
ده بالظبط الـ binary search، بس اللي بيتنص range في array مترتبة:
4 مقارنات بالكتير على 10 عناصر، و 20 على مليون. عشان كده binary search لكل عنصر في array لسه O(n log n) وبيعدّي.
i += 2 مش log n
for (let i = 0; i < n; i += 2) بتلف n / 2 = O(n). الجمع بخطوة ثابتة = O(n). الضرب والقسمة = O(log n).
دي القواعد لوحدها. إزاي تطبقها على function كاملة فيها كذا حاجة؟
القالب: حلّل أي function سطر سطر
اكتب جنب كل سطر بيتنفذ كام مرة وبياخد قد إيه، اجمع، وخد الأكبر:
- أول خطوة: سمّي الأحجام. inputين = متغيرين، n و q.
- سطر واحد فيه حاجتين:
[...nums]نسخة O(n)، وsortO(n log n). والنسخة كمان O(n) memory. new Set(nums)بتضيف n عنصر: O(n) وقت و O(n) memory.- loop على
queries: q لفة مش n. لو كانتnums.includes(x)بدل Set، كانتO(n · q). - n - 1 لفة، والـ
- 1ما بتفرقش: O(n). - شيل الأصغر من نفس المتغير: O(n) جنب O(n log n). بس O(q) تفضل، لأن q مستقل.
- الـ space هو الـ memory الزيادة: النسخة والـ Set. الـ input نفسه ما بيتحسبش.
كل ده loops. طب الـ recursion؟ وإزاي تحسب الـ memory؟
الـ recursion والـ space complexity
Time في الـ recursion = عدد الـ calls × الشغل في كل call. factorial(n) بتنادي نفسها مرة بـ n - 1: n call، O(n). لكن fib(n - 1) + fib(n - 2) بتنادي نفسها مرتين، والشجرة بتتضاعف تقريبًا كل مستوى: حوالي O(2ⁿ)، و fib(40) بتعمل أكتر من 331 مليون call. التفاصيل في Recursion.
Space = الـ memory الزيادة: arrays، Map، Set، وحاجة بتتنسي: الـ call stack. كل call لسه ما رجعش بياخد frame في الـ memory، مستني الـ call اللي بعده.
- بتجمع من 1 لـ n. مفيش arrays، فشكلها O(1) memory. بس ده غلط.
- الـ base case. من غيره الـ calls مش هتقف لحد ما الـ stack يتملي.
- هنا الـ memory. عشان تحسب
n + sumTo(n - 1)، الـ call الحالي لازم يستنى. فعند الـ base case فيه n + 1 frame فوق بعض: الـ space = أعمق نقطة =O(n).
وفي JS الـ stack محدود: في Node حوالي 10 آلاف frame، وساعات أقل. sumTo(100000) بتضرب RangeError: Maximum call stack size exceeded. نفس الحساب بـ loop: O(n) وقت و O(1) space.
فيه حاجة تانية بتخدعك زي الـ recursion: push ساعات بينسخ الـ array كلها، وبرضه بنقول O(1). إزاي؟
Amortized O(1): ليه push سريع
الـ array (زي vector في C++) ليها مكان محجوز اسمه capacity. لو فيه مكان، push بيكتب في الخانة الجاية: O(1). لو المكان خلص، لازم تحجز مكان أكبر وتنسخ كل العناصر: O(n).
capacityالمحجوز، وsizeالمستخدم فعلًا. بنبدأ بـ 1 عشان نشوف الـ resize كتير.- الضعف، مش +1. مع +1 كل push بينسخ الكل:
1 + 2 + ... + n = O(n²). مع الضعف، النسخ عند 1، 2، 4، 8 بس. - النسخ O(size): ده الـ push الغالي.
- الكتابة العادية.
size++post-increment: بنكتب فيbuf[size]وبعدين size يزيد.
الحساب: لـ n push، النسخ = 1 + 2 + 4 + ... وده أقل من 2n. فالشغل الكلي أقل من 3n، يعني أقل من 3 عمليات لكل push في المتوسط. ده الـ "amortized O(1)": push معيّن ممكن يبقى غالي، بس المتوسط ثابت. والـ Map والـ Set بيكبروا بنفس الطريقة.
Best و average و worst case
| الكود | Best | Average | Worst | بنقول إيه |
|---|---|---|---|---|
indexOf | O(1) | O(n) | O(n) | O(n) |
| Map / Set | O(1) | O(1) | O(n) | O(1) average |
| quicksort | O(n log n) | O(n log n) | O(n²) | والـ sort بتاع JS مضمون O(n log n) |
push | O(1) | O(1) | O(n) نادرًا | amortized O(1) |
من غير ما تحدد، المقصود worst case. الاستثناء المتعارف عليه: الـ hash map، بنقول O(1) ونقصد المتوسط.
الـ push سريع فعلًا. بس فيه methods تانية في JS شكلها سريع وهي لأ.
مثال محلول 1: حلّل الكود ده
8 snippets بالترتيب، كل واحد بيضيف trick. احسب الـ complexity قبل ما تفتح الإجابة. كل الإجابات اتأكدت بعدّ العمليات فعليًا.
Snippet 1
الإجابة
O(n + m). ورا بعض بيتجمعوا، و b ممكن تبقى أكبر بكتير من a فما تتشالش.
Snippet 2
الإجابة
O(n²). الداخلية n - i لفة، فالمجموع n(n + 1)/2. لـ n = 1000 بالظبط 500,500.
Snippet 3
الإجابة
O(n). nested آه، بس الداخلية ثابتة: 26n. "nested loops" مش معناها O(n²) أوتوماتيك.
Snippet 4
الإجابة
O(log n). i بيبقى 1، 2، 4، ... لحد n. لـ 10⁵ = 17 لفة، ولـ 10⁹ = 30.
Snippet 5 (trap)
الإجابة
O(n) مش O(n log n). الداخلية مش n كل مرة: 1، 2، 4، ... والمجموع أقل من 2n. لـ n = 1024 بالظبط 1023. نفس حساب الـ dynamic array. الدرس: الداخلية بتعتمد على الخارجية؟ اجمع، ما تضربش.
Snippet 6
الإجابة
O(log n)، أو O(عدد الخانات). كل لفة بتقسم على 10: 98765 = 5 لفّات. هنا n هي قيمة الرقم مش طول array.
Snippet 7 (trap)
الإجابة
O(n²) وقت و O(n) space. الـ sort شكله الأغلى بس هو O(n log n). الغالي فعلًا includes جوه الـ loop. الـ fix: [...new Set(nums)].sort((a, b) => a - b) = O(n log n).
Snippet 8
الإجابة
Time O(2ⁿ) تقريبًا (بالظبط حوالي 1.618ⁿ): fib(30) = 2.7 مليون call، و fib(40) = 331 مليون. Space O(n) بس، لأن الـ stack فيه فرع واحد في أي لحظة، وأعمق فرع طوله n. الـ O(n) في Dynamic Programming 1.
تحليل كود جاهز سهل. الأصعب: تختار بين كذا حل لنفس المسألة.
مثال محلول 2: Contains Duplicate بتلات طرق
فيه رقم ظهر أكتر من مرة؟ رجّع true أو false.
الجديد هنا: مفيش حل "الأحسن" في كل حاجة. فيه trade-off بين الـ time والـ space، وإنت اللي بتختار.
- الـ constraint: n لحد 10⁵: O(n²) ≈ 5 × 10⁹ = TLE.
- Brute force: كل زوج.
O(n²)وقت،O(1)space. - Sort: بعد الترتيب، المتساويين جنب بعض، فقارن كل عنصر باللي قبله بس.
O(n log n). - Set: "شفته قبل كده؟" = سؤال Set.
O(n)وقت بسO(n)space.
الطريقة التانية: sort
- النسخة عشان ما نعدّلش الـ input، ودي O(n) space. لو مسموح تعدّل، رتّب
numsنفسها. والـ comparator عادة ما تتنازلش عنها. - من 1 لأننا بنقارن باللي قبله: loop C من الفصل الأول، n - 1 زوج جيران.
- لو اتنين جنب بعض متساويين: تكرار. لو ولا زوج، مفيش تكرار خالص، لأن الـ sort بيجمّع المتساويين.
الطريقة التالتة: Set
- الذاكرة: كل رقم عدّينا عليه.
- السؤال قبل الإضافة. لو سألنا بعد، كل رقم هيلاقي نفسه.
hasO(1) average، وده اللي بيخلّي الكل O(n). - مش موجود، فنضيفه عشان أي تكرار بعدين يلاقيه.
| الطريقة | Time | Space | ملاحظات |
|---|---|---|---|
| Brute force | O(n²) | O(1) | TLE على 10⁵. قوله بس. |
| Sort + جيران | O(n log n) | O(1) لو عدّلت، O(n) لو نسخت | لو الـ memory محدودة. |
| Set | O(n) | O(n) | الأسرع، و early return. |
| new Set(nums).size !== nums.length | O(n) | O(n) | سطر، بس دايمًا بيلف على الكل. |
| Input | المتوقع | ليه |
|---|---|---|
| [5] | false | عنصر واحد: loop الـ sort ما بتدخلش. |
| [-1, -1] | true | سالب. |
| [1, 2, 3, 4] | false | worst case: بيلف على الكل. |
الجاي: الغلطات اللي الناس بتقع فيها وهي بتحسب.
غلطات مشهورة
1. "سطر واحد يبقى O(1)"
أي method بتدوّر (includes، indexOf) أو بتنسخ (slice، spread) أو بتحرّك (shift، splice) جواها loop. احسبها.
2. O(n²) بدل O(n · m)
كل input ليه متغير، وإلا هتظلم حل كويس أو العكس.
3. نسيت الـ recursion stack
الـ space = أعمق نقطة. ولو العمق ممكن 10⁵، كمان خطر RangeError.
4. i += 2 على إنه log n
الجمع بخطوة ثابتة بيقسم على ثابت. الضرب هو اللي بيدّي log.
5. تشيل متغير مستقل
الحدود بتتشال لما تكون من نفس المتغير بس.
6. Math.max(...arr) على array كبيرة
مش TLE، ده RangeError في حدود مئات الآلاف. على 10⁵ أو أكتر: loop.
جرّب نفسك.
اختبر نفسك
for (let i = 1; i < n; i *= 3) الـ complexity بتاعتها؟
- O(n)
- O(n / 3)
- O(log n)
- O(1)
1، 3، 9، 27: log₃ n لفة، والـ base مش بيفرق. الـ n / 3 لو i += 3.
الـ constraint n <= 2000. حل O(n²) هيعدّي؟
- آه، 4 × 10⁶ عملية، أقل من 10⁸ بكتير
- لأ، أي O(n²) بياخد TLE
- على حسب اللغة بس
- لأ، لازم O(n log n)
2000² = 4 × 10⁶. الـ O(n²) بيبقى مشكلة من حوالي 10⁴ وطالع.
الـ space بتاعة sumTo(n) الـ recursive؟
- O(1)، مفيش arrays
- O(log n)
- O(n)، n frame مستنيين في الـ call stack
- O(n²)
كل call بيستنى اللي بعده، فعند الـ base case فيه n + 1 frame. الـ space = أعمق نقطة.
ليه push O(1) مع إنه ساعات بينسخ الـ array كلها؟
- عشان الـ engine سريع
- الـ capacity بتتضاعف، فالنسخ نادر ومجموعه أقل من 2n: المتوسط ثابت (amortized)
- عشان JS ما بتنسخش arrays
- غلط، هو O(n)
النسخ عند 1، 2، 4، 8، ... ومجموعهم أقل من 2n. الشغل الكلي أقل من 3n على n push.
BFS على 10⁵ node والـ queue بـ shift(). المشكلة؟
- مفيش، shift O(1)
- كل shift بيحرّك الباقي، فالـ BFS ممكن يبقى O(n²)
- shift بيرجّع آخر عنصر
- الـ queue لازم تبقى Set
shift O(n). استخدم head index.
تمرين: فكّر قبل ما تفتح
رجّع الأرقام الموجودة في الاتنين، كل رقم مرة، بأي ترتيب. واحد كتب الحل ده: احسب الـ complexity، وبعدين حسّنه.
تلميح 1
فيه اتنين includes جوه الـ loop: على nums2 (طولها m) وعلى res. فالحالي O(n · m).
تلميح 2
السؤالين اللي بيتكرروا: "موجود في nums2؟" و "حطيته قبل كده؟". الاتنين أسئلة Set.
الحل
O(n + m) وقت و O(n) space. والـ Set التاني حل التكرار من غير includes. القاعدة: كل includes جوه loop هي Set مستنية تتعمل.
دلوقتي على LeetCode، بالترتيب.
اتمرن على LeetCode بالترتيب
في كل مسألة: اكتب الـ complexity المسموحة من الـ constraint كـ comment، وقول الـ brute force وليه مش كفاية. وبعد ما تحل، اكتب الـ time والـ space وليه.
- Fibonacci Numberالـ recursive O(2ⁿ) وبعدين loop O(n). شوف الفرق على n = 30.
- Contains Duplicateالمثال المحلول: التلات طرق والـ trade-off.
- Two SumO(n²) لـ O(n) بـ Map. من غير
indexOfجوه الـ loop. - Intersection of Two Arraysالتمرين: O(n · m) لـ O(n + m).
- Single Numberمطلوب O(1) space، فالـ Set مش مقبول. فكّر في الـ XOR.
- Binary Searchأول O(log n) بإيدك. عدّ المقارنات.
- Sqrt(x)x لحد 2³¹: loop لحد x مستحيلة. الـ constraint بيقولك log n.
- Valid Perfect Squarebinary search على الإجابة تاني.
- Count Negative Numbers in a Sorted MatrixO(m · n) عادي، و O(m + n) بالترتيب. احسب الاتنين.
- Maximum SubarrayO(n³) لـ O(n²) لـ O(n): الفرق بين التلاتة واضح جدًا هنا.
خلّصتهم؟ الفصل كله في صفحة واحدة تحت.
الخلاصة
| السؤال | الإجابة |
|---|---|
| n لحد 10⁵؟ | O(n log n) أو أحسن. |
| n لحد 20؟ | exponential مقبول. |
| nested loops يبقى O(n²) دايمًا؟ | لأ: الداخلية ثابتة؟ متغير تاني؟ بتتضاعف؟ |
| Map و Set؟ | O(1) average. |
| shift؟ | O(n). للـ queue: head index. |
| الـ output بيتحسب في الـ space؟ | غالبًا لأ، بس قولها: "O(1) extra, not counting the output". |
الفصل الجاي: JavaScript للانترفيو. هنا شفنا JS وهي بتبطّأ الكود من غير ما تقولك. الفصل الجاي النوع التاني: JS وهي بتطلّع إجابة غلط من غير error، زي [10, 9, 1].sort() و Array(3).fill([]) و if (map.get(x)) لما القيمة 0. وإنت جاي من C++، دي أكتر حاجات هتوقعك.