جافا سكريبت خوارزميات وهياكل البيانات

تحتوي هذا مقالة على أمثلة عديدة تستند إلى الخوارزميات الشائعة وهياكل البيانات في الجافا سكريبت.

كل خوارزمية وهياكل البيانات لها برنامج README منفصل خاص بها مع التفسيرات والروابط ذات الصلة لمزيد من القراءة (بما في ذلك تلك إلى مقاطع فيديو YouTube).

اقرأ هذا في لغات أخرى: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türk, Italiana, Tiếng Việt, Deutsch

☝ ملاحضة هذا المشروع مخصص للاستخدام لأغراض التعلم والبحث فقط ، و ** ليست ** معدة للاستخدام في الإنتاج

هياكل البيانات

هياكل البيانات هي طريقة خاصة لتنظيم البيانات وتخزينها في جهاز الكمبيوتر بحيث يمكن الوصول إليها وتعديلها بكفاءة. بتعبير أدق ، هيكل البيانات هو مجموعة من البيانات القيم والعلاقات فيما بينها والوظائف أو العمليات التي يمكن تطبيقها عليها البيانات.

B - مبتدئ, A - المتقدمة

• B قائمة مرتبطة
• B قائمة مرتبطة بشكل مضاعف
• B طابور, Queue
• B كومة
• B جدول التجزئة
• B كومة -الحد الأقصى والحد الأدنى من إصدارات الكومة
• B طابور الأولوية
• A تري
• A شجرة
  • A شجرة البحث الثنائية
  • A شجرة AVL
  • A شجرة الأحمر والأسود
  • A شجرة القطعة - مع أمثلة على استفسارات النطاق الأدنى / الأقصى / المجموع
  • A شجرة فينويك (شجرة ثنائية مفهرسة)
• A Graph (كلاهما موجه وغير موجه)
• A مجموعة منفصلة
• A مرشح بلوم

الخوارزميات

الخوارزمية هي تحديد لا لبس فيه لكيفية حل فئة من المشاكل. أنه مجموعة من القواعد التي تحدد بدقة تسلسل العمليات.

B - مبتدئ ، A - متقدم

الخوارزميات حسب الموضوع

• رياضيات

  • B معالجة البت
  • B عاملي
  • B رقم فيبوناتشي - الإصدارات الكلاسيكية والمغلقة
  • B اختبار البدائية (طريقة تقسيم المحاكمة)
  • B الخوارزمية الإقليدية - احسب القاسم المشترك الأكبر (GCD)
  • B أقل مضاعف مشترك (LCM)
  • B منخل إراتوستينس - إيجاد جميع الأعداد الأولية حتى أي حد معين
  • B هي قوة اثنين - تحقق مما إذا كان الرقم هو قوة اثنين (الخوارزميات الساذجة والبتية)
  • B مثلث باسكال
  • B عدد مركب - الأعداد المركبة والعمليات الأساسية معهم
  • B راديان ودرجة - راديان لدرجة التحويل والعكس
  • B تشغيل سريع
  • B طريقة هورنر - تقييم متعدد الحدود
  • A قسم صحيح
  • A الجذر التربيعي - طريقة نيوتن
  • A خوارزمية ليو هوي π - π حسابات تقريبية على أساس N-gons
  • A تحويل فورييه المنفصل - حلل وظيفة الوقت (إشارة) في الترددات التي يتكون منها

• مجموعات

  • B المنتج الديكارتي - منتج من مجموعات متعددة
  • B فيشر ييتس شافل - التقليب العشوائي لتسلسل محدود
  • A مجموعة الطاقة - جميع المجموعات الفرعية للمجموعة (حلول البت والتتبع التراجعي)
  • A التباديل (مع وبدون التكرار)
  • A مجموعات (مع وبدون التكرار)
  • A أطول نتيجة مشتركة (LCS)
  • A أطول زيادة متتالية
  • A أقصر تسلسل فائق مشترك (SCS)
  • A مشكلة حقيبة الظهر - "0/1" و "غير منضم"
  • A الحد الأقصى من Subarray -إصدارات "القوة الغاشمة" و "البرمجة الديناميكية" (كادان)
  • A مجموع الجمع - ابحث عن جميع التركيبات التي تشكل مبلغًا محددًا

• سلاسل

  • B مسافة هامنج - عدد المواقف التي تختلف فيها الرموز
  • A المسافة ليفنشتاين - الحد الأدنى لمسافة التحرير بين تسلسلين
  • A خوارزمية كنوث - موريس - برات (خوارزمية KMP) - بحث السلسلة الفرعية (مطابقة النمط)
  • A خوارزمية Z - بحث سلسلة فرعية (مطابقة النمط)
  • A خوارزمية رابين كارب - بحث السلسلة الفرعية
  • A أطول سلسلة فرعية مشتركة
  • A مطابقة التعبير العادي

• عمليات البحث

  • B البحث الخطي
  • B بحث سريع (أو حظر البحث) - ابحث في مصفوفة مرتبة
  • B بحث ثنائي - البحث في مجموعة مرتبة
  • B بحث الاستيفاء - البحث في مجموعة مرتبة موزعة بشكل موحد

• فرز

  • B Bubble Sort
  • B Selection Sort
  • B Insertion Sort
  • B Heap Sort
  • B Merge Sort
  • B Quicksort - عمليات التنفيذ في المكان وغير في المكان
  • B Shellsort
  • B Counting Sort
  • B Radix Sort

• القوائم المرتبطة

  • B Straight Traversal
  • B Reverse Traversal

• الأشجار

  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)

• الرسوم البيانية

  • B Depth-First Search (DFS)
  • B Breadth-First Search (BFS)
  • B Kruskal’s Algorithm - إيجاد الحد الأدنى من شجرة الامتداد (MST) للرسم البياني الموزون غير الموجه
  • A Dijkstra Algorithm -إيجاد أقصر المسارات لجميع رؤوس الرسم البياني من رأس واحد
  • A Bellman-Ford Algorithm - إيجاد أقصر المسارات لجميع رؤوس الرسم البياني من رأس واحد
  • A Floyd-Warshall Algorithm - إيجاد أقصر المسارات بين جميع أزواج الرؤوس
  • A Detect Cycle - لكل من الرسوم البيانية الموجهة وغير الموجهة (الإصدارات القائمة على DFS و Disjoint Set)
  • A Prim’s Algorithm - إيجاد الحد الأدنى من شجرة الامتداد (MST) للرسم البياني الموزون غير الموجه
  • A Topological Sorting - طريقة البحث العمق الأول (DFS)
  • A Articulation Points - خوارزمية تارجان (تعتمد على DFS)
  • A Bridges - خوارزمية تعتمد على DFS
  • A Eulerian Path and Eulerian Circuit - خوارزمية فلوري - قم بزيارة كل حافة مرة واحدة بالضبط
  • A Hamiltonian Cycle - قم بزيارة كل قمة مرة واحدة بالضبط
  • A Strongly Connected Components - خوارزمية Kosaraju
  • A Travelling Salesman Problem - أقصر طريق ممكن يزور كل مدينة ويعود إلى المدينة الأصلية

• **التشفير

  • B Polynomial Hash - المتداول دالة التجزئة على أساس متعدد الحدود
  • B Caesar Cipher - استبدال بسيط للشفرات

• التعلم الالي

  • B NanoNeuron - 7 وظائف JS بسيطة توضح كيف يمكن للآلات أن تتعلم بالفعل (الانتشار إلى الأمام / الخلف)

• غير مصنف

  • B Tower of Hanoi
  • B Square Matrix Rotation - خوارزمية في المكان
  • B Jump Game - التراجع ، البرمجة الديناميكية (من أعلى إلى أسفل + من أسفل إلى أعلى) والأمثلة الجشعة
  • B Unique Paths - التراجع والبرمجة الديناميكية والأمثلة القائمة على مثلث باسكال
  • B Rain Terraces - محاصرة مشكلة مياه الأمطار (البرمجة الديناميكية وإصدارات القوة الغاشمة)
  • B Recursive Staircase - احسب عدد الطرق للوصول إلى القمة (4 حلول)
  • A N-Queens Problem
  • A Knight's Tour

الخوارزميات حسب النموذج

النموذج الحسابي هو طريقة أو نهج عام يكمن وراء تصميم الفصل من الخوارزميات. إنه تجريد أعلى من مفهوم الخوارزمية ، تمامًا مثل الخوارزمية هي تجريد أعلى من برنامج الكمبيوتر.

• القوة الغاشمة - انظر في جميع الاحتمالات وحدد الحل الأفضل

  • B Linear Search
  • B Rain Terraces - محاصرة مشكلة مياه الأمطار
  • B Recursive Staircase - احسب عدد الطرق للوصول إلى القمة
  • A Maximum Subarray
  • A Travelling Salesman Problem - أقصر طريق ممكن يزور كل مدينة ويعود إلى المدينة الأصلية
  • A Discrete Fourier Transform - حلل وظيفة الوقت (إشارة) في الترددات التي يتكون منها

• جشع - اختر الخيار الأفضل في الوقت الحالي ، دون أي اعتبار للمستقبل

  • B Jump Game
  • A Unbound Knapsack Problem
  • A Dijkstra Algorithm - إيجاد أقصر مسار لجميع رؤوس الرسم البياني
  • A Prim’s Algorithm - إيجاد الحد الأدنى من شجرة الامتداد (MST) للرسم البياني الموزون غير الموجه
  • A Kruskal’s Algorithm - إيجاد الحد الأدنى من شجرة الامتداد (MST) للرسم البياني الموزون غير الموجه

• فرق تسد - قسّم المشكلة إلى أجزاء أصغر ثم حل تلك الأجزاء

  • B Binary Search
  • B Tower of Hanoi
  • B Pascal's Triangle
  • B Euclidean Algorithm - حساب القاسم المشترك الأكبر (GCD)
  • B Merge Sort
  • B Quicksort
  • B Tree Depth-First Search (DFS)
  • B Graph Depth-First Search (DFS)
  • B Jump Game
  • B Fast Powering
  • A Permutations (مع التكرار وبدونه)
  • A Combinations (مع التكرار وبدونه)

• البرمجة الديناميكية - بناء حل باستخدام الحلول الفرعية التي تم العثور عليها مسبقًا

  • B Fibonacci Number
  • B Jump Game
  • B Unique Paths
  • B Rain Terraces - محاصرة مشكلة مياه الأمطار
  • B Recursive Staircase - احسب عدد الطرق للوصول إلى القمة
  • A Levenshtein Distance - الحد الأدنى لمسافة التحرير بين تسلسلين
  • A Longest Common Subsequence (LCS)
  • A Longest Common Substring
  • A Longest Increasing Subsequence
  • A Shortest Common Supersequence
  • A 0/1 Knapsack Problem
  • A Integer Partition
  • A Maximum Subarray
  • A Bellman-Ford Algorithm - إيجاد أقصر مسار لجميع رؤوس الرسم البياني
  • A Floyd-Warshall Algorithm - إيجاد أقصر المسارات بين جميع أزواج الرؤوس
  • A Regular Expression Matching

• التراجع - على غرار القوة الغاشمة ، حاول إنشاء جميع الحلول الممكنة ، ولكن في كل مرة تقوم فيها بإنشاء الحل التالي الذي تختبره إذا استوفت جميع الشروط ، وعندها فقط استمر في إنشاء الحلول اللاحقة. خلاف ذلك ، تراجع ، واذهب إلى طريق مختلف لإيجاد حل. عادةً ما يتم استخدام اجتياز DFS لمساحة الدولة.

  • B Jump Game
  • B Unique Paths
  • B Power Set - جميع المجموعات الفرعية للمجموعة
  • A Hamiltonian Cycle - قم بزيارة كل قمة مرة واحدة بالضبط
  • A N-Queens Problem
  • A Knight's Tour
  • A Combination Sum - ابحث عن جميع التركيبات التي تشكل مبلغًا محددًا

• ** Branch & Bound ** - تذكر الحل الأقل تكلفة الموجود في كل مرحلة من مراحل التراجع البحث ، واستخدام تكلفة الحل الأقل تكلفة الموجود حتى الآن بحد أدنى لتكلفة الحل الأقل تكلفة للمشكلة ، من أجل تجاهل الحلول الجزئية بتكاليف أكبر من تم العثور على حل بأقل تكلفة حتى الآن. اجتياز BFS عادةً بالاشتراك مع اجتياز DFS لمساحة الحالة يتم استخدام الشجرة.

كيفية استخدام هذا المستودع

تثبيت كل التبعيات

npm install

قم بتشغيل ESLint

قد ترغب في تشغيله للتحقق من جودة الكود.

npm run lint

قم بإجراء جميع الاختبارات

npm test

قم بإجراء الاختبارات بالاسم

npm test -- 'LinkedList'

ملعب

يمكنك اللعب بهياكل البيانات والخوارزميات في ملف . /src/playground/playground.js والكتابة اختبارات لها في ./src/playground/__test__/playground.test.js.

ثم قم ببساطة بتشغيل الأمر التالي لاختبار ما إذا كان كود الملعب الخاص بك يعمل كما هو متوقع:

npm test -- 'playground'

معلومات مفيدة

المراجع

▶ هياكل البيانات والخوارزميات على موقع يوتيوب

Big O Notation

• يتم استخدام Big O notation لتصنيف الخوارزميات وفقًا لكيفية نمو متطلبات وقت التشغيل أو المساحة مع نمو حجم الإدخال. قد تجد في الرسم البياني أدناه الأوامر الأكثر شيوعًا لنمو الخوارزميات المحددة في تBig O notation.

مصدر: Big O Cheat Sheet.

فيما يلي قائمة ببعض رموز Big O notation الأكثر استخدامًا ومقارنات أدائها مقابل أحجام مختلفة من بيانات الإدخال.

| Big O Notation | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements | | -------------- | ---------------------------- | ----------------------------- | ------------------------------- | | O(1) | 1 | 1 | 1 | | O(log N) | 3 | 6 | 9 | | O(N) | 10 | 100 | 1000 | | O(N log N) | 30 | 600 | 9000 | | O(N^2) | 100 | 10000 | 1000000 | | O(2^N) | 1024 | 1.26e+29 | 1.07e+301 | | O(N!) | 3628800 | 9.3e+157 | 4.02e+2567 |

تعقيد عمليات بنية البيانات

| Data Structure | Access | Search | Insertion | Deletion | Comments | | ----------------------- | :-------: | :-------: | :-------: | :-------: | :-------- | | Array | 1 | n | n | n | | | Stack | n | n | 1 | 1 | | | Queue | n | n | 1 | 1 | | | Linked List | n | n | 1 | n | | | Hash Table | - | n | n | n |في حالة وجود تكاليف دالة تجزئة مثالية ستكون O (1)| | Binary Search Tree | n | n | n | n | في حالة توازن تكاليف الشجرة ستكون O (log (n))| | B-Tree | log(n) | log(n) | log(n) | log(n) | | | Red-Black Tree | log(n) | log(n) | log(n) | log(n) | | | AVL Tree | log(n) | log(n) | log(n) | log(n) | | | Bloom Filter | - | 1 | 1 | - |الإيجابيات الكاذبة ممكنة أثناء البحث|

تعقيد خوارزميات فرز الصفيف

| Name | Best | Average | Worst | Memory | Stable | Comments | | --------------------- | :-------------: | :-----------------: | :-----------------: | :-------: | :-------: | :-------- | | Bubble sort | n | n2 | n2 | 1 | نعم | | | Insertion sort | n | n2 | n2 | 1 | نعم | | | Selection sort | n2 | n2 | n2 | 1 | لا | | | Heap sort | n log(n) | n log(n) | n log(n) | 1 | لا | | | Merge sort | n log(n) | n log(n) | n log(n) | n | نعم | | | Quick sort | n log(n) | n log(n) | n2 | log(n) | No | عادةً ما يتم إجراء الفرز السريع في مكانه مع مساحة مكدس O (log (n))| | Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | لا | | | Counting sort | n + r | n + r | n + r | n + r | Yes |r - أكبر رقم في المجموعة| | Radix sort | n * k | n * k | n * k | n + k | Yes | ك - طول أطول مفتاح |

مؤيدو المشروع

يمكنك دعم هذا المشروع عبر ❤️️ GitHub أو ❤️️ Patreon.

الناس الذين يدعمون هذا المشروع ∑ = 0

ℹ️ A few more projects and articles about JavaScript and algorithms on trekhleb.dev