אלגוריתמים ויעילות.

הסצנה בשלב הזה

אלגוריתם

מיון בועות

גודל הרשימה

8 בלוקים

סדר התחלתי

מעורבב

הצגת קצב הגדילה

בלוקים

האפשרויות

מוצגות בסדר אקראי.

• נכונה הצעדים מדויקים, אין בהם ניחוש, והם תמיד מסתיימים בתשובה

• שגויה הם כתובים בשפת תכנות

  טעות נפוצה: Takes an algorithm to be a program written in a programming language, rather than the exact steps any person or machine could follow.

  משוב מהקטלוג

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

• שגויה הם מגיעים לתשובה מהר

  משוב

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

• שגויה הם נותנים תשובה נכונה ברוב הפעמים

  משוב

  אלגוריתם צריך לעבוד תמיד, על כל קלט מהסוג שהוא מקבל. שיטה שעובדת “בדרך כלל” היא כלל אצבע.

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

8 בלוקים

סדר התחלתי

מעורבב

הצגת קצב הגדילה

בלוקים

מתקבלת בטווח

± 0.01

ערך קבוע בשאלה

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

8 בלוקים

סדר התחלתי

מעורבב

הצגת קצב הגדילה

בלוקים

האפשרויות

מוצגות בסדר אקראי.

• נכונה הבלוק הגבוה ביותר עומד בקצה הימני

• שגויה כל השורה ממוינת

  טעות נפוצה: Thinks a single pass of bubble sort along the row leaves it sorted.

  משוב מהקטלוג

  מעבר אחד של מיון בועות מבטיח רק דבר אחד: הבלוק הגבוה ביותר נסחף עד הקצה הימני. שאר הבלוקים זזים לכל היותר מקום אחד שמאלה. לכן צריך עוד מעבר, ועוד אחד, וכל מעבר נעצר מקום אחד לפני הקודם. בשורה הפוכה של שמונה בלוקים יש שבעה מעברים: $7 + 6 + \cdots + 1 = 28$$7 + 6 + \cdots + 1 =$$28$⁠ השוואות.

• שגויה הבלוק הנמוך ביותר עומד בקצה השמאלי

  משוב

  הבלוק הנמוך זז לכל היותר מקום אחד שמאלה בכל מעבר: הוא מנצח רק בהשוואה אחת, עם השכן שמשמאלו.

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

8 בלוקיםקבוע

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

מתקבלת בטווח

± 0.01

מחושבת מהסצנה בהגדרה של השלב

Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

תשובות שגויות שהשאלה מזהה

• 64 ± 0.01

  טעות נפוצה: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.

  משוב מהקטלוג

  כדי להשוות כל זוג פעם אחת, כל בלוק נפגש עם כל אחד מ־$n - 1$⁠ האחרים, וזה $n(n-1)$⁠, אבל כך כל זוג נספר פעמיים, פעם מכל צד. לכן מספר הזוגות הוא $\dfrac{n(n-1)}{2}$⁠: לשמונה בלוקים $\dfrac{8 \times 7}{2} = 28$$\dfrac{8 \times 7}{2} =$$28$⁠, לא $64$⁠. זה בסדר גודל של $n^2$⁠, אבל לא $n^2$⁠ עצמו.

• 7 ± 0.01

  טעות נפוצה: Thinks a single pass of bubble sort along the row leaves it sorted.

  משוב מהקטלוג

  מעבר אחד של מיון בועות מבטיח רק דבר אחד: הבלוק הגבוה ביותר נסחף עד הקצה הימני. שאר הבלוקים זזים לכל היותר מקום אחד שמאלה. לכן צריך עוד מעבר, ועוד אחד, וכל מעבר נעצר מקום אחד לפני הקודם. בשורה הפוכה של שמונה בלוקים יש שבעה מעברים: $7 + 6 + \cdots + 1 = 28$$7 + 6 + \cdots + 1 =$$28$⁠ השוואות.

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

8 בלוקיםקבוע

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

מתקבלת בטווח

± 0.01

מחושבת מהסצנה בהגדרה של השלב

Swaps the whole sort makes (merge sort moves instead and makes none)/nodes/sort/outputs/swaps

תשובות שגויות שהשאלה מזהה

• 64 ± 0.01

  טעות נפוצה: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.

  משוב מהקטלוג

  כדי להשוות כל זוג פעם אחת, כל בלוק נפגש עם כל אחד מ־$n - 1$⁠ האחרים, וזה $n(n-1)$⁠, אבל כך כל זוג נספר פעמיים, פעם מכל צד. לכן מספר הזוגות הוא $\dfrac{n(n-1)}{2}$⁠: לשמונה בלוקים $\dfrac{8 \times 7}{2} = 28$$\dfrac{8 \times 7}{2} =$$28$⁠, לא $64$⁠. זה בסדר גודל של $n^2$⁠, אבל לא $n^2$⁠ עצמו.

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

8 בלוקיםקבוע

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

אחרי נעילת הניבוי הסצנה משתנה

סדר התחלתי

כמעט ממויןקבוע

ואז הסצנה מראה: 13 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועות

גודל הרשימה

16 בלוקיםקבוע

סדר התחלתי

כמעט ממויןקבוע

הצגת קצב הגדילה

בלוקים

האפשרויות

• נכונה מיון הכנסה

• שגויה מיון מהיר

  טעות נפוצה: Thinks quicksort is always the fastest sort, whatever the starting row.

  משוב מהקטלוג

  מיון מהיר מהיר בממוצע, על שורה מעורבבת. הגרסה כאן בוחרת תמיד את הבלוק האחרון כאיבר ציר, ובשורה ממוינת או הפוכה הבלוק הזה הוא הגבוה או הנמוך ביותר: כל חלוקה מורידה רק בלוק אחד, והמיון עושה $\dfrac{n(n-1)}{2}$⁠ השוואות, כמו מיון בועות. ספריות מיון אמיתיות בוחרות ציר אקראי או חציוני כדי להתחמק מזה.

• שגויה מיון מיזוג

  משוב

  מיון מיזוג עושה בערך אותה עבודה על כל שורה: הוא מפצל וממזג בכל מקרה. כאן 34 השוואות.

• שגויה מיון בועות

  משוב

  מיון בועות עוצר מוקדם, אבל רק אחרי מעבר שלם בלי החלפות, ובלוק שצריך לזוז שמאלה זז מקום אחד בכל מעבר. כאן 42 השוואות.

אחרי נעילת הניבוי הסצנה משתנה

אלגוריתם

מיון הכנסה

ואז הסצנה מראה: 19 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון מיזוגקבוע

גודל הרשימה

8 בלוקיםקבוע

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

מתקבלת בטווח

± 0.01

מחושבת מהסצנה בהגדרה של השלב

Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

תשובות שגויות שהשאלה מזהה

• 28 ± 0.01

  טעות נפוצה: Thinks every sorting algorithm does the same amount of work on the same list, since they all end with the same sorted row.

  משוב

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

• 64 ± 0.01

  טעות נפוצה: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.

  משוב מהקטלוג

  כדי להשוות כל זוג פעם אחת, כל בלוק נפגש עם כל אחד מ־$n - 1$⁠ האחרים, וזה $n(n-1)$⁠, אבל כך כל זוג נספר פעמיים, פעם מכל צד. לכן מספר הזוגות הוא $\dfrac{n(n-1)}{2}$⁠: לשמונה בלוקים $\dfrac{8 \times 7}{2} = 28$$\dfrac{8 \times 7}{2} =$$28$⁠, לא $64$⁠. זה בסדר גודל של $n^2$⁠, אבל לא $n^2$⁠ עצמו.

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועות

גודל הרשימה

16 בלוקיםקבוע

סדר התחלתי

מעורבבקבוע

הצגת קצב הגדילה

בלוקים

האפשרויות

• נכונה בדיוק 72

• שגויה פחות, כי מיון הכנסה מהיר יותר

  משוב

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

• שגויה יותר

  משוב

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

אחרי נעילת הניבוי הסצנה משתנה

אלגוריתם

מיון הכנסה

ואז הסצנה מראה: 72 · Swaps the whole sort makes (merge sort moves instead and makes none)/nodes/sort/outputs/swaps

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון מהירקבוע

גודל הרשימה

16 בלוקיםקבוע

סדר התחלתי

מעורבב

הצגת קצב הגדילה

בלוקים

האפשרויות

• נכונה הוא יעשה 120 השוואות, כמו מיון בועות

• שגויה הוא יעשה פחות מ־57, כי שורה הפוכה מסודרת יותר

  טעות נפוצה: Thinks quicksort is always the fastest sort, whatever the starting row.

  משוב מהקטלוג

  מיון מהיר מהיר בממוצע, על שורה מעורבבת. הגרסה כאן בוחרת תמיד את הבלוק האחרון כאיבר ציר, ובשורה ממוינת או הפוכה הבלוק הזה הוא הגבוה או הנמוך ביותר: כל חלוקה מורידה רק בלוק אחד, והמיון עושה $\dfrac{n(n-1)}{2}$⁠ השוואות, כמו מיון בועות. ספריות מיון אמיתיות בוחרות ציר אקראי או חציוני כדי להתחמק מזה.

• שגויה בערך אותו דבר, כי מיון מהיר תמיד מהיר

  טעות נפוצה: Thinks quicksort is always the fastest sort, whatever the starting row.

  משוב מהקטלוג

  מיון מהיר מהיר בממוצע, על שורה מעורבבת. הגרסה כאן בוחרת תמיד את הבלוק האחרון כאיבר ציר, ובשורה ממוינת או הפוכה הבלוק הזה הוא הגבוה או הנמוך ביותר: כל חלוקה מורידה רק בלוק אחד, והמיון עושה $\dfrac{n(n-1)}{2}$⁠ השוואות, כמו מיון בועות. ספריות מיון אמיתיות בוחרות ציר אקראי או חציוני כדי להתחמק מזה.

אחרי נעילת הניבוי הסצנה משתנה

סדר התחלתי

הפוך

ואז הסצנה מראה: 120 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועות

גודל הרשימה

32 בלוקיםקבוע

סדר התחלתי

מעורבבקבוע

הצגת קצב הגדילה

בלוקים

נקרא מהסצנה בנקודה

Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

הגדרה אחת שמגיעה למטרה

אלגוריתם

מיון מיזוג

רמז

פתרון מלא

הסצנה בשלב הזה

הגדילה בכל צעד

2 ×קבוע

מספר הצעדים

1

סולם רגיל / סולם לוגריתמי

סולם רגיל

מתקבלת בטווח

± 0.01

ערך קבוע בשאלה

תשובות שגויות שהשאלה מזהה

• 500 ± 0.01

  טעות נפוצה: Mixes up the worst case with the average case: gives half the list as the most a linear search can take.

  משוב מהקטלוג

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

• 10 ± 0.01

  טעות נפוצה: Thinks binary search works on any list, sorted or not.

  משוב מהקטלוג

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

פתרון מלא

הסצנה בשלב הזה

הגדילה בכל צעד

2 ×קבוע

מספר הצעדים

1

סולם רגיל / סולם לוגריתמי

סולם רגיל

האפשרויות

מוצגות בסדר אקראי.

• נכונה היא ממוינת

• שגויה שום דבר: זה עובד על כל רשימה

  טעות נפוצה: Thinks binary search works on any list, sorted or not.

  משוב מהקטלוג

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

• שגויה האורך שלה הוא חזקה של 2

  משוב

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

• שגויה היא קצרה

  משוב

  דווקא ברשימות ארוכות חיפוש בינארי מנצח הכי בגדול.

פתרון מלא

הסצנה בשלב הזה

הגדילה בכל צעד

2 ×קבוע

מספר הצעדים

1

סולם רגיל / סולם לוגריתמי

סולם רגיל

נקרא מהסצנה בנקודה

Growth: the last column, g^n/nodes/board/outputs/growthValue

הגדרה אחת שמגיעה למטרה

מספר הצעדים

10

רמז

פתרון מלא

הסצנה בשלב הזה

הגדילה בכל צעד

2 ×קבוע

מספר הצעדים

10קבוע

סולם רגיל / סולם לוגריתמי

סולם רגיל

האפשרויות

• נכונה 11

• שגויה 20

  טעות נפוצה: Thinks doubling the list doubles the number of steps a binary search takes.

  משוב מהקטלוג

  כל צעד של חיפוש בינארי חוצה את הרשימה. רשימה כפולה צריכה רק חציה אחת נוספת כדי לחזור לגודל הקודם, ולכן מספר הצעדים עולה באחד: 1024 שמות דורשים 10 צעדים, ו־2048 דורשים 11. זו התכונה של הלוגריתם: $\log_2 (2n) = \log_2 n + 1$$\log_2 (2n) =$$\log_2 n + 1$⁠.

• שגויה עדיין 10

  משוב

  עשר חציות מקטינות 2048 רק עד 2 שמות; צריך עוד אחת.

אחרי נעילת הניבוי הסצנה משתנה

מספר הצעדים

11קבוע

ואז הסצנה מראה: 2048 · Growth: the last column, g^n/nodes/board/outputs/growthValue

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

פתרון מלא

הסצנה בשלב הזה

הגדילה בכל צעד

2 ×קבוע

מספר הצעדים

10

סולם רגיל / סולם לוגריתמי

סולם לוגריתמי

מתקבלת בטווח

± 0.5

ערך קבוע בשאלה

תשובות שגויות שהשאלה מזהה

• 6 ± 0.5

  טעות נפוצה: Counts halvings with powers of ten, taking about 6 steps for a million because a million is 10⁶.

  משוב מהקטלוג

  חיפוש בינארי חוצה, ולכן סופרים חזקות של 2, לא של 10. מיליון הוא $10^6$⁠, אבל כל צעד מקטין פי שניים ולא פי עשרה. $2^{10} = 1024$⁠, כלומר עשר חציות מקטינות פי אלף בערך, ועשרים חציות פי מיליון בערך: $2^{20} = 1{,}048{,}576$$2^{20} =$$1{,}048{,}576$⁠. לכן $\log_2 10^6 \approx 20$$\log_2 10^6 \approx$$20$⁠.

• 500000 ± 0.5

  טעות נפוצה: Mixes up the worst case with the average case: gives half the list as the most a linear search can take.

  משוב

  500000 הוא הממוצע של חיפוש סדרתי. חיפוש בינארי משליך חצי מהרשימה בכל בדיקה.

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

16 בלוקים

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

האפשרויות

• נכונה בערך פי ארבעה: 496

• שגויה פי שניים: 240

  טעות נפוצה: Expects every algorithm's work to double when its input doubles.

  משוב מהקטלוג

  רק עבודה שגדלה ליניארית, כמו חיפוש סדרתי, מוכפלת כשהרשימה מוכפלת. מיון בועות משווה זוגות, ומספר הזוגות גדל בערך כמו $n^2$⁠: רשימה כפולה היא בערך פי ארבעה השוואות, ‏120 לשישה־עשר בלוקים ו־496 לשלושים ושניים. לכן אלגוריתם שנראה זריז על עשרה פריטים יכול להיתקע על מיליון.

• שגויה 136: שישה־עשר בלוקים נוספים

  טעות נפוצה: Expects every algorithm's work to double when its input doubles.

  משוב מהקטלוג

  רק עבודה שגדלה ליניארית, כמו חיפוש סדרתי, מוכפלת כשהרשימה מוכפלת. מיון בועות משווה זוגות, ומספר הזוגות גדל בערך כמו $n^2$⁠: רשימה כפולה היא בערך פי ארבעה השוואות, ‏120 לשישה־עשר בלוקים ו־496 לשלושים ושניים. לכן אלגוריתם שנראה זריז על עשרה פריטים יכול להיתקע על מיליון.

אחרי נעילת הניבוי הסצנה משתנה

גודל הרשימה

32 בלוקים

ואז הסצנה מראה: 496 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון מיזוגקבוע

גודל הרשימה

16 בלוקים

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

האפשרויות

• נכונה קצת יותר מפי שניים

• שגויה בערך פי ארבעה, כמו מיון בועות

  משוב

  מיון מיזוג לא משווה כל זוג. הוא ממזג רמה אחר רמה, ומספר הרמות, $\log_2 n$⁠, עולה רק באחד כשהרשימה מוכפלת.

• שגויה בדיוק פי שניים

  משוב

  קרוב, אבל יש גם רמה נוספת של מיזוגים: לא $2 \times 32 = 64$⁠ אלא קצת יותר.

אחרי נעילת הניבוי הסצנה משתנה

גודל הרשימה

32 בלוקים

ואז הסצנה מראה: 80 · Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

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

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

64 בלוקיםקבוע

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

גדילהקבוע

מתקבלת בטווח

± 0.01

מחושבת מהסצנה בהגדרה של השלב

N(n − 1)/2: comparing every pair once, the orange ribbon/nodes/sort/outputs/everyPair

תשובות שגויות שהשאלה מזהה

• 4096 ± 0.01

  טעות נפוצה: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.

  משוב מהקטלוג

  כדי להשוות כל זוג פעם אחת, כל בלוק נפגש עם כל אחד מ־$n - 1$⁠ האחרים, וזה $n(n-1)$⁠, אבל כך כל זוג נספר פעמיים, פעם מכל צד. לכן מספר הזוגות הוא $\dfrac{n(n-1)}{2}$⁠: לשמונה בלוקים $\dfrac{8 \times 7}{2} = 28$$\dfrac{8 \times 7}{2} =$$28$⁠, לא $64$⁠. זה בסדר גודל של $n^2$⁠, אבל לא $n^2$⁠ עצמו.

• 4032 ± 0.01

  טעות נפוצה: Counts n × n comparisons for comparing every pair, counting each pair twice and a block against itself.

  משוב מהקטלוג

  כדי להשוות כל זוג פעם אחת, כל בלוק נפגש עם כל אחד מ־$n - 1$⁠ האחרים, וזה $n(n-1)$⁠, אבל כך כל זוג נספר פעמיים, פעם מכל צד. לכן מספר הזוגות הוא $\dfrac{n(n-1)}{2}$⁠: לשמונה בלוקים $\dfrac{8 \times 7}{2} = 28$$\dfrac{8 \times 7}{2} =$$28$⁠, לא $64$⁠. זה בסדר גודל של $n^2$⁠, אבל לא $n^2$⁠ עצמו.

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועות

גודל הרשימה

64 בלוקים

סדר התחלתי

מעורבב

הצגת קצב הגדילה

גדילה

האפשרויות

מוצגות בסדר אקראי.

• נכונה $O(n^2)$⁠

• שגויה $O(\tfrac12 n^2 - \tfrac12 n)$⁠

  טעות נפוצה: Keeps the constant factors and smaller terms inside big-O, writing O(½n² − ½n) instead of O(n²).

  משוב מהקטלוג

  O גדולה מתארת רק איך העבודה גדלה כש־$n$⁠ גדל, ולכן משמיטים כפולות קבועות ואיברים שגדלים לאט יותר. ב־$\tfrac12 n^2 - \tfrac12 n$⁠ האיבר $n^2$⁠ שולט: כשמכפילים את $n$⁠ פי עשרה, העבודה גדלה בערך פי מאה, מה שלא יהיה המקדם. לכן מיון בועות הוא $O(n^2)$⁠.

• שגויה $O(\tfrac12 n^2)$⁠

  טעות נפוצה: Keeps the constant factors and smaller terms inside big-O, writing O(½n² − ½n) instead of O(n²).

  משוב מהקטלוג

  O גדולה מתארת רק איך העבודה גדלה כש־$n$⁠ גדל, ולכן משמיטים כפולות קבועות ואיברים שגדלים לאט יותר. ב־$\tfrac12 n^2 - \tfrac12 n$⁠ האיבר $n^2$⁠ שולט: כשמכפילים את $n$⁠ פי עשרה, העבודה גדלה בערך פי מאה, מה שלא יהיה המקדם. לכן מיון בועות הוא $O(n^2)$⁠.

• שגויה $O(n)$⁠

  טעות נפוצה: Expects every algorithm's work to double when its input doubles.

  משוב מהקטלוג

  רק עבודה שגדלה ליניארית, כמו חיפוש סדרתי, מוכפלת כשהרשימה מוכפלת. מיון בועות משווה זוגות, ומספר הזוגות גדל בערך כמו $n^2$⁠: רשימה כפולה היא בערך פי ארבעה השוואות, ‏120 לשישה־עשר בלוקים ו־496 לשלושים ושניים. לכן אלגוריתם שנראה זריז על עשרה פריטים יכול להיתקע על מיליון.

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון בועותקבוע

גודל הרשימה

16 בלוקים

סדר התחלתי

הפוךקבוע

הצגת קצב הגדילה

בלוקים

נקרא מהסצנה בנקודה

Comparisons the whole sort makes on the first row/nodes/sort/outputs/comparisons

הגדרה אחת שמגיעה למטרה

גודל הרשימה

20 בלוקים

רמז

פתרון מלא

הסצנה בשלב הזה

אלגוריתם

מיון מיזוג

גודל הרשימה

64 בלוקים

סדר התחלתי

מעורבב

הצגת קצב הגדילה

גדילה

האפשרויות

מוצגות בסדר אקראי.

• נכונה מחשב ב, עם מיון מיזוג

• שגויה מחשב א, כי הוא מהיר פי מאה

  טעות נפוצה: Thinks a faster computer makes up for a slow algorithm.

  משוב מהקטלוג

  מחשב מהיר פי מאה מקצר את הזמן פי מאה, ולא יותר. אלגוריתם טוב יותר יכול לקצר אותו פי אלפים, וההפרש גדל עם הרשימה. למיון של מיליון פריטים, מיון בועות עושה בערך $5 \times 10^{11}$⁠ השוואות, ומיון מיזוג כ־$2 \times 10^7$⁠: פי עשרים וחמישה אלף פחות. שום שדרוג חומרה לא סוגר פער כזה.

• שגויה בערך יחד

  טעות נפוצה: Thinks a faster computer makes up for a slow algorithm.

  משוב מהקטלוג

  מחשב מהיר פי מאה מקצר את הזמן פי מאה, ולא יותר. אלגוריתם טוב יותר יכול לקצר אותו פי אלפים, וההפרש גדל עם הרשימה. למיון של מיליון פריטים, מיון בועות עושה בערך $5 \times 10^{11}$⁠ השוואות, ומיון מיזוג כ־$2 \times 10^7$⁠: פי עשרים וחמישה אלף פחות. שום שדרוג חומרה לא סוגר פער כזה.

רמז

פתרון מלא