تحتوي هذا مقالة على أمثلة عديدة تستند إلى الخوارزميات الشائعة وهياكل البيانات في الجافا سكريبت.
كل خوارزمية وهياكل البيانات لها برنامج 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-gonsA
تحويل فورييه المنفصل - حلل وظيفة الوقت (إشارة) في الترددات التي يتكون منهامجموعات
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
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 - خوارزمية تعتمد على DFSA
Eulerian Path and Eulerian Circuit - خوارزمية فلوري - قم بزيارة كل حافة مرة واحدة بالضبطA
Hamiltonian Cycle - قم بزيارة كل قمة مرة واحدة بالضبطA
Strongly Connected Components - خوارزمية KosarajuA
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 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 | ك - طول أطول مفتاح |
الناس الذين يدعمون هذا المشروع ∑ = 0
ℹ️ A few more projects and articles about JavaScript and algorithms on trekhleb.dev
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。