⚡
The Big-O Cheat Sheet
| Algorithm / Structure | Best Case | Average Case | Worst Case | Space | Notes |
|---|---|---|---|---|---|
| SORTING | |||||
| Insertion Sort | O(N) | O(N^2) | O(N^2) | O(1) | Great for small/almost sorted arrays. |
| Shellsort | O(N) | O(N^1.5) | O(N^2) | O(1) | Depends on gap sequence. |
| Heapsort | O(N log N) | O(N log N) | O(N log N) | O(1) | In-place but unstable. |
| Mergesort | O(N log N) | O(N log N) | O(N log N) | O(N) | Stable, good for external sorting. |
| Quicksort | O(N log N) | O(N log N) | O(N^2) | O(log N) | Fastest in practice (Randomized). |
| DATA STRUCTURES (Search/Insert/Delete) | |||||
| BST (Unbalanced) | O(log N) | O(log N) | O(N) | O(N) | Degenerates to linked list. |
| Hash Table | O(1) | O(1) | O(N) | O(N) | Unordered. Depends on load factor. |
| Binary Heap | O(1) (FindMin) | O(log N) | O(log N) | O(N) | Priority Queue implementation. |
🧠
Algorithm Design Strategies
Greedy (الجشع)
اتخاذ أفضل قرار محلي (Local) في كل خطوة.
- Dijkstra: اختر أقرب عقدة غير زائرة.
- Prim/Kruskal: اختر أرخص حافة.
- Huffman: ادمج أقل تكرارين.
- تحذير: لا يضمن الحل الأمثل دائماً (مثل Coin Change).
Divide & Conquer (فرق تسد)
تقسيم المشكلة لمشاكل فرعية مستقلة، حلها، ثم دمجها.
- Mergesort: اقسم، رتب، ادمج.
- Quicksort: قسّم حول Pivot، رتب الأطراف.
- Binary Tree Traversals: زر الجذر، ثم اليسار، ثم اليمين.
Dynamic Programming (DP)
حل المشاكل الفرعية المتداخلة مرة واحدة وتخزينها (Memoization).
- Fibonacci: بدلاً من $O(2^N)$ تصبح $O(N)$.
- Shortest Path (Floyd-Warshall): لكل الأزواج.
- 0/1 Knapsack: الحل الأمثل الذي يعجز عنه الـ Greedy.
Backtracking (التراجع)
البحث الشامل (Brute Force) بذكاء. جرب، إذا فشلت، تراجع وجرب غيره.
- Maze Solving: حل المتاهات.
- N-Queens: توزيع الملكات.
- Game Trees (Minimax): الشطرنج و Tic-Tac-Toe.
🔑
Key Concepts Recap
Modules 6-7: Trees & BST ▼
- BST Property: اليسار < الأب < اليمين.
- Deletion (2 children): استبدل بأصغر قيمة في اليمين (Successor).
- Traversals: Inorder (يعطي ترتيباً تصاعدياً)، Postorder (لتقييم التعبيرات)، Preorder (للنسخ).
Module 8: Hashing & Heaps ▼
- Hashing: الوصول في $O(1)$. حل التصادم: Separate Chaining (قوائم) أو Open Addressing (مصفوفة).
- Heap (Min-Heap): شجرة كاملة، الأب $\le$ الأبناء. الجذر هو الأصغر دائماً.
- Heap Index: الأب عند $i$، الأبناء عند $2i$ و $2i+1$.
Module 11: Graph Algorithms ▼
- Topological Sort: ترتيب المهام (Indegree = 0). يعمل فقط على DAG (بدون دورات).
- Shortest Path: BFS (بدون وزن)، Dijkstra (أوزان موجبة)، Bellman-Ford (أوزان سالبة).
- MST: Prim (ابدأ بعقدة وكبّر الشجرة)، Kruskal (اختر الحواف ورتبها).