✓ בחינם✓ ללא הגבלה✓ בלי פרסומות
הרבה כלים כאלה ברשת מוגבלים ומלאים בפרסומות. כאן לא, וגם בלי הרשמה – מתוך רצון לעשות חסד.
מחשבון סיבוכיות: Big-O במספרים
O(n²) נשמע מופשט – עד שרואים שעבור מיליון איברים זה כמעט 3 שעות. בוחרים n ורואים את ההבדל, ועד איזה גודל הפתרון עוד עומד בזמן.
| סיבוכיות | פעולות | זמן | n מקסימלי ב- שנ׳ |
|---|
מבני נתונים – כמה עולה כל פעולה
| מבנה | גישה | חיפוש | הכנסה | מחיקה |
|---|---|---|---|---|
| מערך | O(1) | O(n) | O(n) | O(n) |
| מערך דינמי (סוף) | O(1) | O(n) | O(1)* | O(1) |
| רשימה מקושרת | O(n) | O(n) | O(1)** | O(1)** |
| מחסנית / תור | O(n) | O(n) | O(1) | O(1) |
| טבלת hash | — | O(1)* | O(1)* | O(1)* |
| עץ חיפוש מאוזן | O(log n) | O(log n) | O(log n) | O(log n) |
| עץ חיפוש לא מאוזן | O(n) | O(n) | O(n) | O(n) |
| ערימה (heap) | O(1) מינ׳ | O(n) | O(log n) | O(log n) |
* בממוצע / amortized. ** כשכבר מחזיקים מצביע למקום. בעץ לא מאוזן – המקרה הגרוע.
מיונים
| מיון | הכי טוב | ממוצע | הכי גרוע | זיכרון | יציב |
|---|---|---|---|---|---|
| Bubble / Insertion | O(n) | O(n²) | O(n²) | O(1) | ✓ |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | ✗ |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ |
| Counting / Radix | O(n+k) | O(n+k) | O(n+k) | O(n+k) | ✓ |
יציב = איברים שווים נשארים באותו סדר. k = טווח הערכים. אין מיון השוואות מהיר מ-O(n log n) במקרה הגרוע.
הזמנים הם סדר גודל: הקבועים, המטמון והשפה משנים הרבה. הכלל של "בערך 10⁸ פעולות לשנייה" מקובל בתחרויות ובמבחנים.
🎬 סיבוכיות Big-O – ככה זה עובד
💛 באהבה ממיזם הכלים של גילעד רחמים · מיזם חינמי להנגשה. לא הכול זה כסף: רעיון, תוכן או עזרה בהפצה, או שותפות במיזם.
Big-O במספרים: כמה זמן באמת ייקח
בוחרים את גודל הקלט n, מגבלת זמן, וכמה פעולות בשנייה (Python, Java ו-C++ או C++ מהיר). הטבלה מראה לכל סיבוכיות, מ-O(log n) ועד O(2ⁿ), כמה פעולות זה, כמה זמן, ועד איזה n עוד עומדים בזמן.
טבלאות לחזרה
בדף יש טבלה של מבני נתונים, כמה עולה גישה, חיפוש, הכנסה ומחיקה במערך, ברשימה מקושרת, בטבלת hash, בעץ ובערימה. ויש טבלת מיונים: מקרה טוב, ממוצע וגרוע, זיכרון ויציבות. אפשר להדפיס דף סיכום.
הזמנים הם סדר גודל, והכלל של בערך 10⁸ פעולות לשנייה מקובל בתחרויות ובמבחנים. לראות מיון עובד: מיונים בתנועה. לתרגול: סימולטור ראיון.
דוגמה
נניח n = 100,000 ומגבלה של שנייה אחת. O(n log n) הוא בערך 1.7 מיליון פעולות, שעוברות מהר בכל שפה. O(n²) הוא 10 מיליארד פעולות, שלא יעברו בשנייה גם ב-C++. ככה יודעים מראש אם האלגוריתם יעבור, לפני שכותבים קוד. זה חוסך הרבה ניסוי וטעייה.
למבחן, לתחרות ולראיון
בראיון עבודה ובתחרויות תכנות שואלים מה הסיבוכיות של הפתרון, ואם הוא יעבור במגבלת הזמן. הטבלה עונה על זה במספרים, והטבלאות של מבני הנתונים והמיונים נותנות את מה שצריך לזכור בעל פה.
Python, Java או C++
המהירות תלויה בשפה: Python איטית יותר, Java ו-C++ מהירות יותר. בוחרים את השפה שלכם, והטבלה מתעדכנת. המספרים הם סדר גודל, ולא מדידה של מחשב מסוים.
למה זה בחינם
הכלים של גילעד רחמים נבנים כחסד: בלי תשלום, בלי פרסומות ובלי הרשמה, כדי שכל אחד יוכל להשתמש בהם. מי שרוצה לעזור, שולח את הדף לחבר שזה יכול לעזור לו. חסר לכם כלי? אפשר לבקש כלי חדש.
שאלות ותשובות
מה זה סיבוכיות זמן?
כמה הזמן גדל כשהקלט גדל. O(n) גדל באותו קצב, O(n²) בריבוע. במחשבון רואים את זה בשניות.
עד איזה n פתרון O(n²) עובר בשנייה?
בערך 10,000 ב-C++ לפי 10⁸ פעולות לשנייה. המחשבון מחשב לפי מה שבוחרים.
מה הסיבוכיות של טבלת hash?
חיפוש, הכנסה ומחיקה בממוצע O(1). זה מופיע בטבלה עם הערות.
אפשר להדפיס?
כן, יש כפתור "להדפיס דף סיכום".
עד איזה n יעבור O(n²) בשנייה?
בערך עד n של 10,000, אם מניחים כ-10⁸ פעולות בשנייה. המחשבון מראה את זה לכל מהירות שבוחרים.
הדף הזה בחינם?
כן. הכול כאן בחינם, בלי הרשמה ובלי פרסומות.
זה עובד גם בטלפון?
כן. הדף נפתח בדפדפן של הטלפון ושל המחשב, ולא צריך להתקין שום דבר.
עוד כלים בחינם שאולי יעזרו
לכל הכלים של ״כלים למתכנתים בעברית: AI, NVIDIA, סטודנטים וראיונות״ ←
