Big-O والـ Complexitytime & space complexity · growth rates · hidden costs in JavaScript

قبل ما تكتب الحل، تقدر تعرف هياخد TLE ولا لأ. Big-O بيعدّ الحل بيعمل كام خطوة، وبيشوف العدد ده بيكبر إزاي لما الـ input يكبر، من غير ما تشغّل حاجة.

قبله: إزاي تحل أي مسألة بيمهّد لـ: JavaScript للانترفيو وكل الـ patterns بعده

هتطلع من الفصل ده وإنت عارف

  • Big-O بيقيس إيه بالظبط، وليه بنشيل الثوابت والحدود الصغيرة.
  • تحسب الـ complexity لأي كود: loops ورا بعض، جوه بعض، بتنص، بتعتمد على بعض، و recursion.
  • تحوّل سطر الـ constraints لـ complexity مسموحة بقاعدة الـ 10⁸.
  • تحسب الـ space ومنها الـ recursion stack، وتفهم ليه push O(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.

تشبيه فرح: لو كل ضيف بياخد كارت على الباب، 10 ضيوف = 10 كروت، و 1000 = 1000. الشغل بيكبر زي الضيوف: O(n). لكن لو كل ضيف لازم يسلّم على كل ضيف، الـ 10 = 45 سلام، والـ 1000 = حوالي نص مليون. الضيوف زادوا 100 مرة، والسلامات أكتر من 10,000 مرة: O(n²).

شوف ده على 6 أرقام بس: function بتعدّي على كل عنصر، وواحدة بتعدّي على كل زوج:

nsingle: npairs: n(n - 1)/2pairs على 10⁸/ثانية
6615ولا حاجة
1,0001,000499,5005 ملّي ثانية
100,000100,000≈ 5 × 10⁹حوالي 50 ثانية: TLE

Big-O هو اسم "شكل" النمو ده: O(n) و O(n²). ومن غير ما تشغّل حاجة، عرفت إن التانية مش هتعدّي مع n = 10⁵.

طب إمتى تحسبها، وإزاي تحوّل سطر الـ constraints لرقم تحكم بيه؟

إمتى تحسبها، وقاعدة الـ 10⁸

احسبها لما: تقرا الـ constraintsتقول الـ brute forceبتختار بين حلين Time Limit ExceededMemory Limit Exceeded"can you do better?"
ومش محتاج تقلق لو: n صغير وثابت (26 حرف، sudoku 9×9)الفرق بين 2n و 3n

السيرفر بيعمل تقريبًا 10⁸ عملية بسيطة في الثانية، والـ time limit غالبًا ثانية أو اتنين. فالسؤال: الحل مع أكبر n هيعمل كام عملية؟

الرقم ده سقف، مش هدف loop فاضية بتعمل 10⁸ لفة في حوالي 0.1 ثانية في Node على جهاز سريع. بس العمليات الحقيقية (Map، إنشاء arrays، function calls) أبطأ بمراحل. اعتبر 10⁸ السقف، واستهدف 10⁷ لو تقدر.
لو n لحدالمسموحعمليات تقريبًاحلول بتطلع كده
10O(n!)3.6 × 10⁶كل الـ permutations
20O(2ⁿ)10⁶كل الـ subsets، backtracking
500O(n³)1.25 × 10⁸تلات loops جوه بعض
5,000O(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,623binary 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. وبعدين:

  1. نشيل الحدود الصغيرة: 3n² + 5n + 20 → 3n².
  2. نشيل الثابت: 3n² → n². فالإجابة O(n²).
n3n²5n20نسبة الـ 3n² من الكل
10300502081%
1,0003,000,0005,0002099.83%
100,0003 × 10¹⁰500,0002099.998%

الحدود الصغيرة بتختفي لما n يكبر، وده الوقت الوحيد اللي بيفرق. والثابت بيتغيّر حسب الجهاز وطريقة الكتابة، لكن شكل النمو لأ: لو n اتضاعف، أي O(n²) بيتضرب في 4، سواء الثابت 3 ولا 300.

التعريف بكلام بسيط O(g(n)) معناها: من عند n كبيرة كفاية، عدد العمليات مش هيعدّي c × g(n) لثابت ما c. فيه كمان Θ (النمو بالظبط) و Ω (أرضية)، بس في الانترفيو الناس بتقول O وتقصد النمو بالظبط.

عرفنا بنشيل إيه. يلا نشوف الـ classes المشهورة بالأرقام.

الـ complexity classes المشهورة

Classالإحساسمثالعمليات على n = 10⁵الوقت على 10⁸/ثانية
O(1)بصّة واحدةarr[i]، push، map.get1ولا حاجة
O(log n)بتنص المسألة كل خطوةbinary search17ولا حاجة
O(n)كل عنصر مرةone pass10⁵1 ملّي ثانية
O(n log n)n مرة شغل log nsort≈ 1.7 × 10⁶17 ملّي ثانية
O(n²)كل عنصر مع كل عنصرnested loops10¹⁰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 صغير كده؟ لعبة "خمّن الرقم" من 1 لـ 100، وصاحبك بيقول "أكبر" أو "أصغر". لو بتخمّن النص كل مرة، بتشيل نص الاحتمالات: 100، 50، 25، 12، 6، 3، 1. يعني 7 تخمينات بالكتير. ومن 1 لمليون؟ 20 بس. ده log₂ n.

والـ 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.

  1. الفرق كله في الـ update: Math.floor(i / 2) مش i++. الـ floor عشان i يفضل integer، والـ >= 1 عشان لفة i = 1 تتحسب، وبعدها i يبقى 0 فتقف.
  2. شغل ثابت. لو هنا loop على n، الكل يبقى O(n log n).
  3. النتيجة ⌊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 سطر سطر

اكتب جنب كل سطر بيتنفذ كام مرة وبياخد قد إيه، اجمع، وخد الأكبر:

  1. أول خطوة: سمّي الأحجام. inputين = متغيرين، n و q.
  2. سطر واحد فيه حاجتين: [...nums] نسخة O(n)، و sort O(n log n). والنسخة كمان O(n) memory.
  3. new Set(nums) بتضيف n عنصر: O(n) وقت و O(n) memory.
  4. loop على queries: q لفة مش n. لو كانت nums.includes(x) بدل Set، كانت O(n · q).
  5. n - 1 لفة، والـ - 1 ما بتفرقش: O(n).
  6. شيل الأصغر من نفس المتغير: O(n) جنب O(n log n). بس O(q) تفضل، لأن q مستقل.
  7. الـ 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. بتجمع من 1 لـ n. مفيش arrays، فشكلها O(1) memory. بس ده غلط.
  2. الـ base case. من غيره الـ calls مش هتقف لحد ما الـ stack يتملي.
  3. هنا الـ 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).

تشبيه لو كل ما فرد يدخل العيلة تنقل لشقة فيها أوضة زيادة واحدة، هتقضي عمرك بتنقل عفش. لكن لو كل ما الشقة تتملي تنقل لشقة ضعف المساحة، النقل مكلف بس نادر: عند 1، 2، 4، 8 أفراد. ولو قسمت تعب النقل على الكل، نصيب كل فرد صغير وثابت.
  1. capacity المحجوز، و size المستخدم فعلًا. بنبدأ بـ 1 عشان نشوف الـ resize كتير.
  2. الضعف، مش +1. مع +1 كل push بينسخ الكل: 1 + 2 + ... + n = O(n²). مع الضعف، النسخ عند 1، 2، 4، 8 بس.
  3. النسخ O(size): ده الـ push الغالي.
  4. الكتابة العادية. 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

الكودBestAverageWorstبنقول إيه
indexOfO(1)O(n)O(n)O(n)
Map / SetO(1)O(1)O(n)O(1) average
quicksortO(n log n)O(n log n)O(n²)والـ sort بتاع JS مضمون O(n log n)
pushO(1)O(1)O(n) نادرًاamortized O(1)

من غير ما تحدد، المقصود worst case. الاستثناء المتعارف عليه: الـ hash map، بنقول O(1) ونقصد المتوسط.

الـ push سريع فعلًا. بس فيه methods تانية في JS شكلها سريع وهي لأ.

الـ hidden costs في JavaScript

أخطر جزء في الفصل: سطر واحد مش معناه O(1). methods كتير جواها loop كاملة، ولو جوه loop بتاعتك، الحل بيبقى O(n²) وإنت فاكره O(n). الأرقام تحت متقاسة بـ Node، والمهم فيها الفرق.

العمليةالتكلفةليه
arr[i]، length، at(-1)، push، popO(1)آخر الـ array أو عنوان مباشر
shift، unshift، spliceO(n)بيحرّك العناصر
slice، [...arr]، concatO(n)نسخة جديدة
includes، indexOf، find، someO(n)loop مستخبية
map، filter، reduce، forEachO(n)loop على كل عنصر
sortO(n log n)
Map / Set: get، set، has، add، deleteO(1) avghash table
Object.keys، values، entriesO(k)array جديدة بكل المفاتيح
s.slice، split، join، s1 === s2O(length)نسخ أو مقارنة حرف حرف

1. includes أو indexOf جوه loop

الـ includes بتمشي عنصر عنصر، فكل لفة من الـ n بتعمل لحد n مقارنة. الـ Set بيسأل الـ hash table مباشرة: الفرق 500 مرة.

2. shift و unshift

بعد ما الـ shift يشيل الأول، لازم يحرّك كل اللي وراه خانة. وده بالظبط اللي بيحصل في BFS، عشان كده الـ head هتشوفه في كل BFS في الدليل. التفاصيل في Queue و Deque.

3. slice جوه recursion أو loop

ونفس الكلام لـ splice وإنت بتشيل عناصر في loop. الحل filter مرة واحدة، أو read/write pointers زي Two Pointers.

4. spread أو concat جوه loop

اللفة رقم k بتنسخ k عنصر، فالمجموع O(n²). الكود ده شكله "functional" ونضيف، وده اللي بيخلّيه trap.

5. بناء string وإنت بتقرا منه

الـ strings في JS immutable: أي تعديل بيعمل string جديد. V8 عنده trick: الـ += لوحده بيتخزن كقطع من غير نسخ، فبيبقى سريع. بس أول ما تقرا منه وإنت بتبنيه (زي s[s.length - 1])، لازم يلزق القطع، وده نسخ كامل في كل لفة:

القاعدة المضمونة في أي engine: ابني في array، و join مرة واحدة في الآخر.

6. Math.max(...arr) بيقع

في Node، 120 ألف عنصر عدّوا و 200 ألف وقعوا، والرقم بيختلف من engine للتاني. وده مش TLE، ده Runtime Error، فهتتلخبط وإنت بتدوّر. مع constraint 10⁵ أو أكتر، استخدم loop.

وكمان: sort جوه loop رتّب مرة واحدة برا. sort جوه loop على n = O(n² log n). ولو محتاج أصغر عنصر من مجموعة بتتغير كل شوية، ده heap.

كده عندك كل القواعد. نتمرن عليها: حلّل 8 snippets.

مثال محلول 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 بتلات طرق

Contains Duplicate

easyLeetCode 217

فيه رقم ظهر أكتر من مرة؟ رجّع true أو false.

Input: [1, 2, 3, 1] → true Input: [1, 2, 3, 4] → false Input: [3, 7, 1, 9, 7, 2] → true Constraints: 1 <= n <= 10⁵, values can be negative

الجديد هنا: مفيش حل "الأحسن" في كل حاجة. فيه trade-off بين الـ time والـ space، وإنت اللي بتختار.

  1. الـ constraint: n لحد 10⁵: O(n²) ≈ 5 × 10⁹ = TLE.
  2. Brute force: كل زوج. O(n²) وقت، O(1) space.
  3. Sort: بعد الترتيب، المتساويين جنب بعض، فقارن كل عنصر باللي قبله بس. O(n log n).
  4. Set: "شفته قبل كده؟" = سؤال Set. O(n) وقت بس O(n) space.

الطريقة التانية: sort

  1. النسخة عشان ما نعدّلش الـ input، ودي O(n) space. لو مسموح تعدّل، رتّب nums نفسها. والـ comparator عادة ما تتنازلش عنها.
  2. من 1 لأننا بنقارن باللي قبله: loop C من الفصل الأول، n - 1 زوج جيران.
  3. لو اتنين جنب بعض متساويين: تكرار. لو ولا زوج، مفيش تكرار خالص، لأن الـ sort بيجمّع المتساويين.

الطريقة التالتة: Set

  1. الذاكرة: كل رقم عدّينا عليه.
  2. السؤال قبل الإضافة. لو سألنا بعد، كل رقم هيلاقي نفسه. has O(1) average، وده اللي بيخلّي الكل O(n).
  3. مش موجود، فنضيفه عشان أي تكرار بعدين يلاقيه.
الطريقةTimeSpaceملاحظات
Brute forceO(n²)O(1)TLE على 10⁵. قوله بس.
Sort + جيرانO(n log n)O(1) لو عدّلت، O(n) لو نسختلو الـ memory محدودة.
SetO(n)O(n)الأسرع، و early return.
new Set(nums).size !== nums.lengthO(n)O(n)سطر، بس دايمًا بيلف على الكل.
Inputالمتوقعليه
[5]falseعنصر واحد: loop الـ sort ما بتدخلش.
[-1, -1]trueسالب.
[1, 2, 3, 4]falseworst case: بيلف على الكل.
في الانترفيو "Brute force is O(n²). Sorting gives O(n log n) with O(1) extra space if I can modify the input. A hash set gives O(n) time but O(n) space. I'd go with the set unless memory is tight." الجملة الأخيرة (إمتى تختار إيه) هي اللي بتفرق.

الجاي: الغلطات اللي الناس بتقع فيها وهي بتحسب.

غلطات مشهورة

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.

تمرين: فكّر قبل ما تفتح

Intersection of Two Arrays

easyLeetCode 349

رجّع الأرقام الموجودة في الاتنين، كل رقم مرة، بأي ترتيب. واحد كتب الحل ده: احسب الـ complexity، وبعدين حسّنه.

[1, 2, 2, 1], [2, 2] → [2] [4, 9, 5], [9, 4, 9, 8, 4] → [9, 4] (or [4, 9])
تلميح 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 وليه.

خلّصتهم؟ الفصل كله في صفحة واحدة تحت.

الخلاصة

في جملة واحدة Big-O بيعدّ الحل بيعمل كام خطوة لما الـ input يكبر، ويشيل الثوابت والحدود الصغيرة. اضرب في الـ constraint، ولو طلع أكبر من 10⁸ محتاج فكرة تانية. وما تصدّقش إن سطر واحد O(1) قبل ما تعرف بيعمل إيه.
السؤالالإجابة
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++، دي أكتر حاجات هتوقعك.