אלגוריתמים ומבני נתונים ב-JavaScript

מאגר זה מכיל דוגמאות מבוססות JavaScript של אלגוריתמים ומבני נתונים פופולריים רבים.

לכל אלגוריתם ומבנה נתונים יש README משלו עם הסברים קשורים וקישורים לקריאה נוספת (כולל קישורים לסרטוני YouTube).

קרא זאת בשפות אחרות: 简体中文, 繁體中文, 한국어, 日本語, Polski, Français, Español, Português, Русский, Türkçe, Italiana, Bahasa Indonesia, Українська, Arabic, Tiếng Việt, Deutsch, Uzbek

מבני נתונים

מבנה נתונים הוא דרך מסוימת לארגן ולאחסן נתונים במחשב כך שניתן לגשת אליהם ולשנות אותם ביעילות. ליתר דיוק, מבנה נתונים הוא אוסף של ערכי נתונים, היחסים ביניהם, והפונקציות או הפעולות שניתן ליישם על הנתונים.

זכור שלכל מבנה נתונים יש את היתרונות והחסרונות שלו. חשוב לשים לב יותר לסיבה שבגללה אתה בוחר מבנה נתונים מסוים מאשר לאופן היישום שלו.

B - מתחיל, A - מתקדם

• B רשימה מקושרת
• B רשימה מקושרת כפולה
• B תור
• B מחסנית
• B טבלת גיבוב
• B ערימה - גרסאות מקסימום ומינימום
• B תור עדיפויות
• A עץ תחיליות
• A עץ
  • A עץ חיפוש בינארי
  • A עץ AVL
  • A עץ אדום-שחור
  • A עץ מקטעים - עם דוגמאות לשאילתות מינימום/מקסימום/סכום של טווח
  • A עץ פנוויק (עץ בינארי מאונדקס)
• A גרף (מכוון ולא מכוון)
• A קבוצה מופרדת - מבנה נתונים של איחוד-מציאה או מיזוג-מציאה
• A מסנן בלום
• A מטמון LRU - מטמון פחות שימוש לאחרונה (LRU)

אלגוריתמים

אלגוריתם הוא מפרט חד משמעי כיצד לפתור סוג של בעיות. זוהי קבוצה של כללים המגדירים במדויק רצף של פעולות.

B - מתחיל, A - מתקדם

אלגוריתמים לפי נושא

• מתמטיקה

  • B מניפולציה על ביטים - קביעה/עדכון/ניקוי ביטים, הכפלה/חילוק ב-2, הפיכה לשלילי וכו'
  • B נקודה צפה בינארית - ייצוג בינארי של מספרים בנקודה צפה
  • B פקטוריאל
  • B מספר פיבונאצ'י - גרסאות קלאסיות וסגורות
  • B גורמים ראשוניים - מציאת גורמים ראשוניים וספירתם באמצעות משפט הארדי-רמנוג'אן
  • B בדיקת ראשוניות (שיטת החלוקה הניסיונית)
  • B אלגוריתם אוקלידס - חישוב המחלק המשותף הגדול ביותר (GCD)
  • B המכפיל המשותף הקטן ביותר (LCM)
  • B נפה של ארטוסתנס - מציאת כל המספרים הראשוניים עד לגבול כלשהו
  • B האם חזקה של שתיים - בדיקה אם מספר הוא חזקה של שתיים (אלגוריתמים נאיביים וביטיים)
  • B משולש פסקל
  • B מספר מרוכב - מספרים מרוכבים ופעולות בסיסיות עליהם
  • B רדיאן ומעלות - המרה מרדיאנים למעלות ובחזרה
  • B חזקה מהירה
  • B שיטת הורנר - הערכת פולינום
  • B מטריצות - מטריצות ופעולות בסיסיות על מטריצות (כפל, טרנספוזיציה וכו')
  • B מרחק אוקלידי - מרחק בין שתי נקודות/וקטורים/מטריצות
  • A חלוקת מספר שלם
  • A שורש ריבועי - שיטת ניוטון
  • A אלגוריתם π של ליו הוי - חישובי π מקורבים על בסיס N-גונים
  • A התמרת פורייה הבדידה - פירוק פונקציה של זמן (אות) לתדרים המרכיבים אותה

• קבוצות

  • B מכפלה קרטזית - מכפלה של מספר קבוצות
  • B ערבוב פישר-ייטס - תמורה אקראית של רצף סופי
  • A קבוצת חזקה - כל תתי הקבוצות של קבוצה (פתרונות ביטיים, מעקב לאחור וקסקדה)
  • A תמורות (עם ובלי חזרות)
  • A צירופים (עם ובלי חזרות)
  • A תת-רצף משותף ארוך ביותר (LCS)
  • A תת-רצף עולה ארוך ביותר
  • A על-רצף משותף קצר ביותר (SCS)
  • A בעיית התרמיל - "0/1" ו"לא מוגבל"
  • A תת-מערך מקסימלי - "כוח ברוטלי" ו"תכנות דינמי" (Kadane) גרסאות
  • A סכום צירוף - מציאת כל הצירופים שיוצרים סכום ספציפי

• מחרוזות

  • B מרחק המינג - מספר העמדות שבהן הסמלים שונים
  • B פלינדרום - בדיקה אם המחרוזת זהה בקריאה לאחור
  • A מרחק לוונשטיין - מרחק העריכה המינימלי בין שתי רצפים
  • A אלגוריתם קנות'-מוריס-פראט (אלגוריתם KMP) - חיפוש תת-מחרוזת (התאמת תבנית)
  • A אלגוריתם Z - חיפוש תת-מחרוזת (התאמת תבנית)
  • A אלגוריתם רבין קארפ - חיפוש תת-מחרוזת
  • A תת-מחרוזת משותפת ארוכה ביותר
  • A התאמת ביטוי רגולרי

• חיפושים

  • B חיפוש לינארי
  • B חיפוש קפיצות (או חיפוש בלוקים) - חיפוש במערך ממוין
  • B חיפוש בינארי - חיפוש במערך ממוין
  • B חיפוש אינטרפולציה - חיפוש במערך ממוין עם התפלגות אחידה

• מיון

  • B מיון בועות
  • B מיון בחירה
  • B מיון הכנסה
  • B מיון ערימה
  • B מיון מיזוג
  • B מיון מהיר - יישומים במקום ולא במקום
  • B מיון צדפות
  • B מיון ספירה
  • B מיון בסיס
  • B מיון דלי

• רשימות מקושרות

  • B מעבר ישר
  • B מעבר הפוך

• עצים

  • B חיפוש לעומק (DFS)
  • B חיפוש לרוחב (BFS)

• גרפים

  • B חיפוש לעומק (DFS)
  • B חיפוש לרוחב (BFS)
  • B אלגוריתם קרוסקל - מציאת עץ פורש מינימלי (MST) עבור גרף לא מכוון משוקלל
  • A אלגוריתם דייקסטרה - מציאת המסלולים הקצרים ביותר לכל קודקודי הגרף מקודקוד יחיד
  • A אלגוריתם בלמן-פורד - מציאת המסלולים הקצרים ביותר לכל קודקודי הגרף מקודקוד יחיד
  • A אלגוריתם פלויד-וורשל - מציאת המסלולים הקצרים ביותר בין כל זוגות הקודקודים
  • A זיהוי מעגל - עבור גרפים מכוונים ולא מכוונים (גרסאות מבוססות DFS וקבוצה מופרדת)
  • A אלגוריתם פרים - מציאת עץ פורש מינימלי (MST) עבור גרף לא מכוון משוקלל
  • A מיון טופולוגי - שיטת DFS
  • A נקודות חיתוך - אלגוריתם טרג'ן (מבוסס DFS)
  • A גשרים - אלגוריתם מבוסס DFS
  • A מסלול ומעגל אוילר - אלגוריתם פלרי - ביקור בכל קשת בדיוק פעם אחת
  • A מעגל המילטון - ביקור בכל קודקוד בדיוק פעם אחת
  • A רכיבים קשירים חזק - אלגוריתם קוסרג'ו
  • A בעיית הסוכן הנוסע - המסלול הקצר ביותר האפשרי שמבקר בכל עיר וחוזר לעיר המוצא

• הצפנה

  • B גיבוב פולינומי - פונקציית גיבוב מתגלגלת המבוססת על פולינום
  • B צופן גדר מסילה - אלגוריתם הצפנת טרנספוזיציה להצפנת הודעות
  • B צופן קיסר - צופן החלפה פשוט
  • B צופן היל - צופן החלפה המבוסס על אלגברה לינארית

• למידת מכונה

  • B NanoNeuron - 7 פונקציות JS פשוטות שמדגימות כיצד מכונות יכולות ללמוד באמת (תפוצה קדימה/אחורה)
  • B k-NN - אלגוריתם סיווג k-השכנים הקרובים ביותר
  • B k-Means - אלגוריתם אשכול k-Means

• עיבוד תמונה

  • B Seam Carving - אלגוריתם שינוי גודל תמונה מודע תוכן

• סטטיסטיקה

  • B משקל אקראי - בחירת פריט אקראי מהרשימה על בסיס משקלי הפריטים

• אלגוריתמים אבולוציוניים

  • A אלגוריתם גנטי - דוגמה לאופן שבו ניתן ליישם אלגוריתם גנטי לאימון מכוניות בחניה עצמית

• לא מסווג

  • B מגדלי האנוי
  • B סיבוב מטריצה ריבועית - אלגוריתם במקום
  • B משחק הקפיצות - דוגמאות למעקב לאחור, תכנות דינמי (מלמעלה למטה + מלמטה למעלה) וחמדני
  • B מסלולים ייחודיים - דוגמאות למעקב לאחור, תכנות דינמי ומבוססות על משולש פסקל
  • B מדרגות גשם - בעיית לכידת מי גשם (גרסאות תכנות דינמי וכוח ברוטלי)
  • B מדרגות רקורסיביות - ספירת מספר הדרכים להגיע לראש (4 פתרונות)
  • B הזמן הטוב ביותר לקנות ולמכור מניות - דוגמאות לחלוקה וכיבוש ומעבר אחד
  • A בעיית N-המלכות
  • A סיור הפרש

אלגוריתמים לפי פרדיגמה

פרדיגמה אלגוריתמית היא שיטה או גישה כללית המונחת בבסיס התכנון של מחלקת אלגוריתמים. זוהי הפשטה גבוהה יותר מהמושג של אלגוריתם, בדיוק כפי שאלגוריתם הוא הפשטה גבוהה יותר מתוכנית מחשב.

• כוח ברוטלי - בודק את כל האפשרויות ובוחר את הפתרון הטוב ביותר

  • B חיפוש לינארי
  • B מדרגות גשם - בעיית לכידת מי גשם
  • B מדרגות רקורסיביות - ספירת מספר הדרכים להגיע לראש
  • A תת-מערך מקסימלי
  • A בעיית הסוכן הנוסע - המסלול הקצר ביותר האפשרי שמבקר בכל עיר וחוזר לעיר המוצא
  • A התמרת פורייה הבדידה - פירוק פונקציה של זמן (אות) לתדרים המרכיבים אותה

• חמדני - בוחר את האפשרות הטובה ביותר בזמן הנוכחי, ללא כל התחשבות בעתיד

  • B משחק הקפיצות
  • A בעיית התרמיל הלא מוגבל
  • A אלגוריתם דייקסטרה - מציאת המסלולים הקצרים ביותר לכל קודקודי הגרף
  • A אלגוריתם פרים - מציאת עץ פורש מינימלי (MST) עבור גרף לא מכוון משוקלל
  • A אלגוריתם קרוסקל - מציאת עץ פורש מינימלי (MST) עבור גרף לא מכוון משוקלל

• חלוקה וכיבוש - מחלק את הבעיה לחלקים קטנים יותר ואז פותר חלקים אלה

  • B חיפוש בינארי
  • B מגדלי האנוי
  • B משולש פסקל
  • B אלגוריתם אוקלידס - חישוב המחלק המשותף הגדול ביותר (GCD)
  • B מיון מיזוג
  • B מיון מהיר
  • B חיפוש לעומק בעץ (DFS)
  • B חיפוש לעומק בגרף (DFS)
  • B מטריצות - יצירה ומעבר על מטריצות בצורות שונות
  • B משחק הקפיצות
  • B חזקה מהירה
  • B הזמן הטוב ביותר לקנות ולמכור מניות - דוגמאות לחלוקה וכיבוש ומעבר אחד
  • A תמורות (עם ובלי חזרות)
  • A צירופים (עם ובלי חזרות)
  • A תת-מערך מקסימלי

• תכנות דינמי - בניית פתרון באמצעות תת-פתרונות שנמצאו קודם לכן

  • B מספר פיבונאצ'י
  • B משחק הקפיצות
  • B מסלולים ייחודיים
  • B מדרגות גשם - בעיית לכידת מי גשם
  • B מדרגות רקורסיביות - ספירת מספר הדרכים להגיע לראש
  • B Seam Carving - אלגוריתם שינוי גודל תמונה מודע תוכן
  • A מרחק לוונשטיין - מרחק העריכה המינימלי בין שתי רצפים
  • A תת-רצף משותף ארוך ביותר (LCS)
  • A תת-מחרוזת משותפת ארוכה ביותר
  • A תת-רצף עולה ארוך ביותר
  • A על-רצף משותף קצר ביותר
  • A בעיית התרמיל 0/1
  • A חלוקת מספר שלם
  • A תת-מערך מקסימלי
  • A אלגוריתם בלמן-פורד - מציאת המסלולים הקצרים ביותר לכל קודקודי הגרף
  • A אלגוריתם פלויד-וורשל - מציאת המסלולים הקצרים ביותר בין כל זוגות הקודקודים
  • A התאמת ביטוי רגולרי

• מעקב לאחור - בדומה לכוח ברוטלי, מנסה לייצר את כל הפתרונות האפשריים, אך בכל פעם שאתה מייצר פתרון הבא אתה בודק אם הוא עומד בכל התנאים, ורק אז ממשיך לייצר פתרונות הבאים. אחרת, חוזר אחורה, והולך בנתיב אחר של מציאת פתרון. בדרך כלל מעבר DFS של מרחב המצבים משמש.

  • B משחק הקפיצות
  • B מסלולים ייחודיים
  • B קבוצת חזקה - כל תתי הקבוצות של קבוצה
  • A מעגל המילטון - ביקור בכל קודקוד בדיוק פעם אחת
  • A בעיית N-המלכות
  • A סיור הפרש
  • A סכום צירוף - מציאת כל הצירופים שיוצרים סכום ספציפי

• סניף וחסום - זוכר את הפתרון בעלות הנמוכה ביותר שנמצא בכל שלב של החיפוש המעקב לאחור, ומשתמש בעלות של הפתרון בעלות הנמוכה ביותר שנמצא עד כה כגבול תחתון על העלות של פתרון בעלות מינימלית לבעיה, על מנת לפסול פתרונות חלקיים עם עלויות גדולות יותר מהפתרון בעלות הנמוכה ביותר שנמצא עד כה. בדרך כלל מעבר BFS בשילוב עם מעבר DFS של עץ מרחב המצבים משמש.

כיצד להשתמש במאגר זה

התקנת כל התלויות

npm install

הרצת ESLint

ייתכן שתרצה להריץ אותו כדי לבדוק את איכות הקוד.

npm run lint

הרצת כל הבדיקות

npm test

הרצת בדיקות לפי שם

npm test -- 'LinkedList'

פתרון בעיות

אם הלינטינג או הבדיקות נכשלים, נסה למחוק את התיקייה node_modules ולהתקין מחדש את חבילות npm:

rm -rf ./node_modules
npm i

בנוסף, ודא שאתה משתמש בגרסת Node נכונה (>=16). אם אתה משתמש ב-nvm לניהול גרסאות Node, תוכל להריץ nvm use מתיקיית השורש של הפרויקט והגרסה הנכונה תיבחר.

שטח משחקים

אתה יכול לשחק עם מבני נתונים ואלגוריתמים בקובץ ./src/playground/playground.js ולכתוב בדיקות עבורו ב-./src/playground/__test__/playground.test.js.

לאחר מכן פשוט הרץ את הפקודה הבאה כדי לבדוק אם קוד שטח המשחקים שלך עובד כמצופה:

npm test -- 'playground'

מידע שימושי

הפניות

• ▶ מבני נתונים ואלגוריתמים ב-YouTube
• ✍🏻 סקיצות של מבני נתונים

סימון ה-O הגדול

סימון ה-O הגדול משמש לסיווג אלגוריתמים לפי כיצד זמן הריצה או דרישות המרחב שלהם גדלים ככל שגודל הקלט גדל. בתרשים שלהלן תוכל למצוא את הסדרים הנפוצים ביותר של צמיחת אלגוריתמים המצוינים בסימון ה-O הגדול.

מקור: Big O Cheat Sheet.

להלן רשימה של כמה מסימוני ה-O הגדול הנפוצים ביותר והשוואות הביצועים שלהם מול גדלים שונים של נתוני קלט.

סימון ה-O הגדול	חישובים ל-10 אלמנטים	חישובים ל-100 אלמנטים	חישובים ל-1000 אלמנטים
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

מורכבות פעולות מבני נתונים

מבנה נתונים	גישה	חיפוש	הכנסה	מחיקה	הערות
מערך	1	n	n	n
מחסנית	n	n	1	1
תור	n	n	1	1
רשימה מקושרת	n	n	1	n
טבלת גיבוב	-	n	n	n	במקרה של פונקציית גיבוב מושלמת, העלויות יהיו O(1)
עץ חיפוש בינארי	n	n	n	n	במקרה של עץ מאוזן, העלויות יהיו O(log(n))
עץ B	log(n)	log(n)	log(n)	log(n)
עץ אדום-שחור	log(n)	log(n)	log(n)	log(n)
עץ AVL	log(n)	log(n)	log(n)	log(n)
מסנן בלום	-	1	1	-	תוצאות חיוביות שגויות אפשריות בעת חיפוש

מורכבות אלגוריתמי מיון מערכים

שם	הטוב ביותר	ממוצע	הגרוע ביותר	זיכרון	יציב	הערות
מיון בועות	n	n2	n2	1	כן
מיון הכנסה	n	n2	n2	1	כן
מיון בחירה	n2	n2	n2	1	לא
מיון ערימה	n log(n)	n log(n)	n log(n)	1	לא
מיון מיזוג	n log(n)	n log(n)	n log(n)	n	כן
מיון מהיר	n log(n)	n log(n)	n2	log(n)	לא	מיון מהיר בדרך כלל מבוצע במקום עם O(log(n)) שטח מחסנית
מיון צדפות	n log(n)	תלוי ברצף הפער	n (log(n))2	1	לא
מיון ספירה	n + r	n + r	n + r	n + r	כן	r - המספר הגדול ביותר במערך
מיון בסיס	n * k	n * k	n * k	n + k	כן	k - אורך המפתח הארוך ביותר

תומכי הפרויקט

אתה יכול לתמוך בפרויקט זה דרך ❤️️ GitHub או ❤️️ Patreon.

אנשים שתומכים בפרויקט זה ∑ = 1

מחבר

@trekhleb

כמה פרויקטים ומאמרים נוספים על JavaScript ואלגוריתמים ב-trekhleb.dev* B [משחק הקפיצות](src/algorithms/uncategor * B [חיפוש בינארי](src/algorithms