Big-O صح: إيه اللي بنقيسه فعلًا؟
Big-O بيوصف معدل نمو الوقت أو الذاكرة مع حجم الـ input، مش الوقت بالثواني. O(n) معناها «لو الـ input اتضاعف، الوقت تقريبًا بيتضاعف». ده بيخليك تتنبأ: الكود اللي شغال كويس على 1,000 عميل هيعمل إيه على مليون؟
| التعقيد | n = 10³ | n = 10⁶ | مثال |
|---|---|---|---|
| O(1) | 1 | 1 | Dictionary lookup (متوسط) |
| O(log n) | ~10 | ~20 | binary search، B-tree index seek |
| O(n) | 10³ | 10⁶ | scan، LINQ Where على List |
| O(n log n) | ~10⁴ | ~2×10⁷ | sorting |
| O(n²) | 10⁶ | 10¹² (ساعات) | loop متداخل، N+1 queries على N عنصر |
قواعد الحساب العملية
- Loops متتالية بتتجمع: O(n) + O(m) = O(n + m). متداخلة بتتضرب: O(n × m).
- بتتجاهل الثوابت والحدود الأصغر: 3n² + 100n = O(n²) — بس الثوابت بتفرق في الواقع (انظر تحت).
- Recursion: عدد الاستدعاءات × الشغل في كل استدعاء. Merge sort: كل مستوى O(n)، وفيه log n مستوى ← O(n log n). الـ Master theorem بيعمم ده: T(n) = a·T(n/b) + f(n).
- الـ hidden loops:
list.Containsوlist.IndexOfوstring.Concatفي loop و.Count()على IEnumerable كلها O(n) مستخبية.
// O(n^2): Contains on a List inside a loop
var result = new List<int>();
foreach (var id in incomingIds) // n
if (!result.Contains(id)) result.Add(id); // Contains is O(n) on List
// O(n): HashSet makes membership O(1) average
var seen = new HashSet<int>();
var unique = incomingIds.Where(seen.Add).ToList(); // Add returns false if already presentWorst مقابل average مقابل amortized
| النوع | بيقول إيه | مثال |
|---|---|---|
| Worst case | ضمان لكل عملية لوحدها، لأسوأ input | Binary search O(log n) دايمًا |
| Average (expected) | متوسط على توزيع inputs أو randomness | Hash table lookup O(1) متوسط، O(n) لو كل المفاتيح اتصادمت |
| Amortized | متوسط على سلسلة عمليات، لأي سلسلة (مش احتمالي) | List.Add: أغلب الإضافات O(1)، أحيانًا O(n) للـ resize، والمتوسط O(1) |
ليه الفرق مهم في الـ backend؟ Amortized O(1) معناه إن عملية واحدة ممكن تاخد وقت طويل. في API بتبني List فيها مليون عنصر، الـ resize الأخير بينسخ نص مليون عنصر وبيعمل allocation كبيرة (ممكن تروح الـ Large Object Heap) ← spike في الـ p99 latency. لو عارف الحجم: new List<T>(capacity).
Amortized analysis بالحساب: الـ dynamic array
Aggregate method: مع مضاعفة السعة، الـ copies عند كل resize هي 1، 2، 4، …، n/2 — مجموعهم أقل من n. فـ n عملية Add كلها أقل من 2n شغل ← O(1) لكل واحدة في المتوسط.
Accounting method: اعتبر كل Add بيدفع 3 «عملات»: واحدة للكتابة، واتنين محوشين. لما الـ array يتملي ويتضاعف، العناصر اللي اتضافت من آخر resize محوشة كفاية لنسخ نفسها ونسخ عنصر قديم. الرصيد عمره ما بيبقى سالب ← التكلفة الـ amortized ثابتة.
ليه مش «+10 كل مرة»؟ لو السعة بتزيد بثابت، الـ copies = 10 + 20 + 30 + … = O(n²/10) ← O(n) لكل Add. المضاعفة (أو أي معامل > 1) هي اللي بتدّي O(1).
نفس التحليل بيشرح: Dictionary resize، StringBuilder، والـ queue المبني من stackين (كل عنصر بيتنقل مرة واحدة بالكتير).
لما الثوابت بتغلب الـ Big-O
- Cache locality: loop على
int[]متتالي أسرع بكتير من linked list بنفس الـ O(n) لأن الـ CPU بيحمّل cache lines. - n صغير: linear search على 8 عناصر غالبًا أسرع من HashSet (حساب الـ hash + indirection).
- I/O بيغلب كل حاجة: query واحدة للـ DB (~1ms) = ملايين عمليات في الذاكرة. N+1 queries مشكلة O(n) round-trips مش O(n) عمليات.
- Allocations: LINQ chain على hot path بتعمل allocations بتضغط على الـ GC — نفس الـ O، تكلفة حقيقية أعلى. قيس بـ BenchmarkDotNet (Performance).
Range queries الثابتة: prefix sums و difference arrays
لو المصفوفة مش بتتغير، أي sum على [l, r] = prefix[r+1] − prefix[l] في O(1) بعد O(n) تجهيز.
long[] BuildPrefix(int[] a)
{
var p = new long[a.Length + 1];
for (int i = 0; i < a.Length; i++) p[i + 1] = p[i] + a[i];
return p;
}
long RangeSum(long[] p, int l, int r) => p[r + 1] - p[l]; // inclusive [l, r]
// 2D: sum of a rectangle in O(1) after O(R*C) preprocessing (inclusion-exclusion)
// S(r1,c1,r2,c2) = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]Difference array (العكس): «زوّد x على كل العناصر من l لـ r» كتير، وبعدين اقرا النتيجة مرة: diff[l] += x; diff[r+1] −= x، وفي الآخر prefix sum على diff. ده مفيد مثلًا لحساب عدد الاشتراكات النشطة في كل يوم من فترات (start, end).
المشكلة: لو فيه updates بين الـ queries، prefix sums محتاجة O(n) لإعادة الحساب بعد كل update. هنا بييجي دور Fenwick و Segment trees.
Fenwick tree (BIT): prefix sums مع updates في O(log n)
كل خانة tree[i] مسؤولة عن مجموع فترة طولها = أصغر bit مضاءة في i (i & −i). الـ prefix sum لحد i بيتجمع من O(log n) خانة بالنزول (i −= i & −i)، والـ update بيعدّل O(log n) خانة بالطلوع (i += i & −i).
public sealed class Fenwick(int n)
{
private readonly long[] _t = new long[n + 1]; // 1-indexed internally
public void Add(int index, long delta) // 0-indexed public API
{
for (int i = index + 1; i < _t.Length; i += i & -i) _t[i] += delta;
}
public long Prefix(int count) // sum of the first `count` elements
{
long s = 0;
for (int i = count; i > 0; i -= i & -i) s += _t[i];
return s;
}
public long Range(int l, int r) => Prefix(r + 1) - Prefix(l); // inclusive [l, r]
}حدوده: Fenwick ممتاز للعمليات اللي ليها «عكس» (جمع وطرح). Range min/max مش بيتعمل بيه ببساطة لأن مفيش «طرح» للـ min. هنا الـ segment tree.
Segment tree: أي عملية associative على range
شجرة كل node فيها نتيجة العملية (sum/min/max/gcd) على فترة، والجذر على المصفوفة كلها، وكل node بيتقسم نصين. أي range [l, r] بيتغطى بـ O(log n) node، والـ point update بيعدّل مسار واحد من الورقة للجذر.
public sealed class MinSegmentTree
{
private readonly int _n;
private readonly int[] _t;
public MinSegmentTree(int[] a)
{
_n = a.Length; _t = new int[2 * _n];
Array.Copy(a, 0, _t, _n, _n); // leaves at [n, 2n)
for (int i = _n - 1; i > 0; i--) _t[i] = Math.Min(_t[2 * i], _t[2 * i + 1]);
}
public void Set(int index, int value)
{
int i = index + _n; _t[i] = value;
for (i /= 2; i >= 1; i /= 2) _t[i] = Math.Min(_t[2 * i], _t[2 * i + 1]);
}
public int Min(int l, int r) // inclusive [l, r]
{
int res = int.MaxValue;
for (l += _n, r += _n + 1; l < r; l /= 2, r /= 2)
{
if ((l & 1) == 1) res = Math.Min(res, _t[l++]);
if ((r & 1) == 1) res = Math.Min(res, _t[--r]);
}
return res;
}
}Lazy propagation: range updates
«زوّد 5 على كل العناصر من 100 لـ 90,000» كـ point updates = O(n log n). مع lazy propagation: لو node فترته كلها جوه الـ update، عدّل قيمته وسجّل «pending +5» عليه وما تنزلش لأولاده؛ ولما query أو update تانية تحتاج تنزل، ادفع الـ pending لأولاده الأول. النتيجة: range update و range query الاتنين O(log n).
أنماط amortized في مسائل الإنترفيو
تلات أنماط بتطلع كتير، وكلهم شكلهم O(n²) أو أسوأ لكن الـ amortized analysis بيثبت إنهم أسرع بكتير. السر في كل مرة: كل عنصر بيدخل ويخرج مرة واحدة بالكتير.
1) Monotonic stack: Next Greater Element
لكل عنصر، أول عنصر على يمينه أكبر منه. Brute force O(n²). بالـ stack: امشي من الشمال، وطول ما العنصر الحالي أكبر من الـ top، يبقى هو «الأكبر التالي» للـ top — pop وسجّل. فيه while جوه for، لكن كل index بيتعمله push مرة و pop مرة بالكتير ← 2n عملية ← O(n).
public static int[] NextGreater(int[] a)
{
var res = Enumerable.Repeat(-1, a.Length).ToArray();
var stack = new Stack<int>(); // indices with decreasing values
for (int i = 0; i < a.Length; i++)
{
while (stack.Count > 0 && a[stack.Peek()] < a[i])
res[stack.Pop()] = a[i]; // each index is popped at most once
stack.Push(i);
}
return res;
}
// Same idea: Daily Temperatures, Largest Rectangle in Histogram, stock span.2) Monotonic deque: Sliding Window Maximum
أقصى قيمة في كل نافذة طولها k. Heap بيدّي O(n log k). Deque بيدّي O(n): احتفظ بـ indices قيمها تنازلية؛ اشيل من الآخر أي عنصر أصغر من الجديد (عمره ما هيبقى max تاني)، واشيل من الأول لو خرج من النافذة. الأول دايمًا هو الـ max.
public static int[] MaxSlidingWindow(int[] a, int k)
{
var dq = new LinkedList<int>(); // indices, values decreasing from front to back
var res = new int[a.Length - k + 1];
for (int i = 0; i < a.Length; i++)
{
while (dq.Count > 0 && a[dq.Last!.Value] <= a[i]) dq.RemoveLast();
dq.AddLast(i);
if (dq.First!.Value <= i - k) dq.RemoveFirst(); // left the window
if (i >= k - 1) res[i - k + 1] = a[dq.First.Value];
}
return res;
}تطبيق مباشر: «أعلى latency في آخر 60 ثانية» لـ dashboard live من غير ما تخزن كل القيم مرتبة.
3) Union-Find بـ path compression و union by rank
Disjoint sets لـ «هل العنصرين في نفس المجموعة؟» مع دمج مستمر (connected components ديناميكيًا، تجميع حسابات مكررة، Kruskal). من غير تحسينات ممكن تبقى شجرة طويلة O(n). مع التحسينين، التكلفة الـ amortized لكل عملية O(α(n)) — α هي inverse Ackermann، ≤ 4 لأي n عملي، يعني ثابت فعليًا.
public sealed class UnionFind
{
private readonly int[] _parent, _rank;
public UnionFind(int n) { _parent = Enumerable.Range(0, n).ToArray(); _rank = new int[n]; }
public int Find(int x) => _parent[x] == x ? x : _parent[x] = Find(_parent[x]); // path compression
public bool Union(int a, int b)
{
int ra = Find(a), rb = Find(b);
if (ra == rb) return false;
if (_rank[ra] < _rank[rb]) (ra, rb) = (rb, ra); // union by rank
_parent[rb] = ra;
if (_rank[ra] == _rank[rb]) _rank[ra]++;
return true;
}
}
// Real use: merging duplicate customer records that share an email OR a phone (entity resolution).تمرين: احسب تعقيد الكود ده
1: loop خارجي i من 1 لـ n، وداخلي j = i; j < n; j *= 2
الحل: الداخلي بيعمل حوالي log(n/i) خطوة. المجموع على i ≤ n log n ← O(n log n) (والتحليل الأدق بيدّي O(n)، لأن مجموع log(n/i) = O(n) — نقطة bonus لو قلتها).
2: recursion T(n) = 2T(n/2) + O(n)
الحل: log n مستوى، كل مستوى O(n) ← O(n log n) (merge sort). ولو T(n) = 2T(n/2) + O(1) ← O(n) (عدد الـ nodes في شجرة binary).
3: endpoint بيعمل foreach على orders وجواه await db.Customers.FindAsync(order.CustomerId)
الحل: O(n) queries للـ DB (N+1). من ناحية Big-O نفس الـ O(n)، لكن الثابت = round-trip شبكة لكل عنصر. الحل: query واحدة بـ join/Include أو WHERE Id IN (...) ← O(1) round-trips. ده المثال اللي بيوضح إن «عدد العمليات المكلفة» أهم من «عدد العمليات».
تختار إيه؟
| الموقف | الهيكل | Query | Update |
|---|---|---|---|
| بيانات ثابتة، range sums | Prefix sums | O(1) | O(n) |
| Range updates كتير ثم قراءة مرة | Difference array | O(n) مرة واحدة | O(1) |
| Prefix/range sums + point updates | Fenwick | O(log n) | O(log n) |
| Range min/max/gcd + updates | Segment tree | O(log n) | O(log n) |
| Range updates + range queries | Segment tree + lazy | O(log n) | O(log n) |
| Static range min (بدون updates) | Sparse table | O(1) | — |
في الـ backend الحقيقي: نادرًا هتكتب segment tree بإيدك — الـ database بيعمل aggregations و indexes. لكن الأفكار بتظهر: time-series rollups (pre-aggregated buckets = prefix-like)، rate limiters بـ sliding windows (عدّادات لكل segment زمني)، و leaderboards (Redis sorted sets = skip list بـ O(log n)). ولو عندك in-memory analytics على ملايين النقط بتتحدث، Fenwick هو أبسط حل صحيح.
أخطاء شائعة
- اعتبار O(1) average ضمان: hash flooding (مفاتيح مصممة تتصادم) بيحوّل الـ Dictionary لـ O(n) — .NET بيستخدم randomized string hashing للحماية.
- نسيان تكلفة الـ resize في الـ hot path: pre-size الـ collections لما الحجم معروف.
- Off-by-one في Fenwick (1-indexed جوه، 0-indexed برّه) — اعزل التحويل في الـ public API زي فوق.
- Segment tree بحجم 2n مع n مش power of 2 في implementations الـ recursive (محتاجة 4n)، أو overflow في الـ sums (استخدم long).
- بناء هيكل معقد لما الـ database ممكن تعمل الـ query بـ index مناسب.
اختبر فهمك
محتاج range minimum مع point updates على 10⁶ عنصر و10⁵ query. الأنسب؟
كود فيه loop على n عنصر وجواه list.Contains على list بتكبر لحد n. التعقيد؟
مسائل إنترفيو محلولة
1 (Easy→Medium): Range Sum Query — Immutable ثم Mutable
Immutable: prefix sums ← O(1) لكل query. Mutable (المحاور ضاف update): prefix sums هتبقى O(n) لكل update. قول الـ trade-off بصوت عالي، وبعدين Fenwick: update و query O(log n). لاحظ إن update في المسألة غالبًا «set value» مش «add» ← احسب الفرق delta = new − old واحتفظ بنسخة من المصفوفة.
2 (Medium): Count of Smaller Numbers After Self
التفكير: Brute force O(n²). امشي من اليمين للشمال، ولكل رقم اسأل «كام رقم أصغر مني شفته؟» = prefix count على القيم. اعمل coordinate compression للقيم (رتّبهم وخد rank)، و Fenwick على الـ ranks: query(rank − 1) ثم add(rank, 1). O(n log n). نفس الفكرة بتحسب عدد الـ inversions.
3 (Medium): Car Pooling / حجوزات — هل السعة اتعدت في أي لحظة؟
التفكير: كل رحلة = +passengers عند البداية، −passengers عند النهاية = difference array على الزمن، وبعدين prefix sum وتأكد إن مفيش لحظة تعدت السعة. O(n + T). لو الأوقات كبيرة جدًا: رتّب الأحداث (sweep line) ← O(n log n). ده نفس منطق «أقصى عدد sessions متزامنة» في الـ analytics.
4 (Senior discussion): leaderboard لمليون لاعب، تحديث score كل ثانية، وطلب «ترتيبي كام؟»
التفكير: sorted list = O(n) لكل update. الخيارات: Redis sorted set (ZADD/ZREVRANK في O(log n)، الأبسط تشغيليًا)، أو Fenwick على buckets الـ scores لو الـ scores أعداد صحيحة في نطاق محدود (rank = عدد اللي score أعلى = suffix count). ناقش الـ sharding (leaderboard لكل منطقة + global تقريبي)، و consistency (ترتيب بتأخير ثانية مقبول؟).
أسئلة إنترفيو
(Junior) إيه معنى amortized O(1)؟
(Mid) ليه Dictionary ممكن يبقى O(n) في lookup؟
(Senior) API بيحسب «أعلى 10 منتجات مبيعًا في آخر ساعة» في كل request وبطيء. تصميمك؟
المراجع والقراءة الإضافية
الدرس بيشرح الفكرة نفسها؛ الروابط دي للتحقق والتعمق والرجوع لتفاصيل الـ API. (محتاجة إنترنت.)
التوثيق الرسمي — Official documentation
مصادر تعليمية ومتقدمة — Third-party & advanced reading
خلصت الدرس وحليت الأسئلة؟ علّم عليه عشان يتحسب في تقدّمك.