... לערך 5, דהיינו, שבסוף התהליך הרשימה תיראה כך: (5,5,5,5,5). ולשם כך עלינו לעשות 9 פעולות של הוספת הערך 1, לכל אחד מהמספרים, כדי שבסופו של תהליך, כל
הערכים יהיו זהים לערך של המספר הגדול ביותר. את זה נעשה באמצעות פעולות ההוספה הבאות: (2+1+1+1, 3+1+1, 3+1+1, 3+1+1, 5). דהיינו, באמצעות 9 פעולות הוספה של הערך 1, נוכל להפוך את כל
הערכים שברשימה לערך הגדול ביותר, שהוא הערך 5. דהיינו, אם אנחנו מבצעים בכל פעם פעולה אחת של הגדלה 1 בלבד, נעשה זאת ... פעם, של הוספת הערך 1, כדי להגדיל את כל המספרים, לערך הגדול ביותר, דהיינו, לבצע 9 פעולות של הגדלה ב 1, כנל. אבל כמו כן, באפשרותך בפעולה אחת, הגדלה של שני
ערכים שונים ב 1. דהיינו, בבת אחת להוסיף בשני מקומות שונים, את הערך 1, כדי ליישר קו שהכל יהיה בערך הגבוה ביותר. לדוגמה כך: או לדוגמה כך: דהיינו, במקום 9 פעולות של הוספת הערך 1, במקום זה נוכל לבצע 5 פעולות של הוספת 1, כדי ליישר את כל
הערכים לערך 5. במהות, בכל פעולה, אנחנו מגדילים 2
ערכים שונים, כל אחד מהם מגדילים אותו בערך 1. כאשר בדוגמה הנל, אנחנו 4 פעמים נעשה הגדלה של שני מספרים שונים בערך 1 ופעם אחת אחרונה, נגדיל רק ערך אחד בלבד, בערך 1, כי כבר אין
ערכים נוספים שצריכים להגדיל. ועד כאן הבנו, שיש לנו רשימת מספרים, שאנחנו צריכים ליישר קו להגדיל את כל
הערכים לערך הגדול ביותר, באמצעות פעולת הוספה של הערך 1 עד שכל
הערכים יהיו זהים ערך הגדול ביותר. ואנחנו יכולים לבצע את זה, או באמצעות פעולת הוספה של 1 בכל פעם, או של 2 פעולות ... עד כאן נראה שהדברים יחסית ברורים. אני אציין ואומר, שבעצם יש לנו כאן במהות 2 תהליכים. 1 - איתור המספר הגדול ביותר. 2 - הגדלת כל המספרים וסכימה של
הערכים וכולי. האם ניתן לבצע את 2 התהליכים האלו תוך כדי ריצה אחת על הרשימה, או שצריך בשלב 1 לעבור על כל הרשימה, כדי ... את פעולות ההגדלה, הסכימה, ההכפלה וכולי? אז לכאורה, אכן צריכים לרוץ על הרשימה, פעמיים. פעם ראשונה כדי לאתר את המספר הגדול ביותר. ורק אחר כך לעבור על כל
הערכים להגדיל אותם וכולי. אבל זאת לא כל האמת. כי בפועל, אפשרי לרוץ פעם אחת על כל הרשימה ולבצע בריצה אחת את הפעולות הבאות: 1 - לנסות לאתר כל המספר הגדול ביותר. 2 - באותה ריצה, לסכום את כל
הערכים שיש לנו ברשימה. דהיינו, הערך במיקום 1 + הערך במיקום 2 + הערך במיקום 3 וכולי, כמו שהם, בלי לבצע שום חישוב ... לדעת מהו המספר הגדול ביותר. ואז מכך נוכל לבצע חישוב של: הערך הגדול ביותר, כפול כמות המספרים ברשימה. ואז נוכל להסיק מכך את הערך המקסימאלי שהיה, אם כל
הערכים ברשימה היו בגודל של הערך הגדול ביותר. לדוגמה במקרה הנל, 50
ערכים 100 שהוא הערך הגדול ביותר, = 5000. עכשיו, אם נסכום את כל המספרים, אז נראה שהערך שלהם הוא X. ואז 5000 פחות X, זה בעצם ההפרש שבין
הערכים הנוכחיים לבין מקרה שבו כל
הערכים היו באותו הגודל המקסימאלי. ו ה X הזה, מייצג את כמות פעולות ההוספה שנצטרך לעשות, כדי להביא את כל המספרים ... לבצע את הפעולות הבאות: (5-2=3) + (5-3=2) + (5-3=2) + (5-3=2) = 9 פעולות אבל מצד האמת, אפשרי לחשב זאת גם כך: (5 5 = 25) דהיינו, המקסימאלי שהיה אם כל
הערכים היו זהים לערך הגדול ביותר, שהוא 5 כנל. (2+3+3+3+5 = 16) דהיינו, סכום נוכחי של כל
הערכים. ואז: 25-16=9. דהיינו, עלינו לבצע 9 הגדלות, כדי ליישר את כל
הערכים כלפי מעלה. במילים אחרות, על ידי ניסוי ידני כמה פעמים של פתירת התרגיל הנל, ניתן לראות שבזמן ריצה O(N) ניתן ... ביותר. האם נדע איך לחשב את זה? כי אם לא, אז ממילא לא נוכל לפתור את השאלה הגדולה. אז איך בעצם יודעים כמה פעמים ניתן לבצע הגדלה כפולה, דהיינו, שמגדילים שני
ערכים בבת אחת? תשובה: נגיע לזה בהמשך. אבל כרגע נחזור לנתח את השאלה המקורית. אז בעצם עד כה, היה לנו תהליך של למצוא את ... של לחשב כמה פעמים נצטרך לבצע הגדלה של כל המספרים בכל פעם מספר אחד, עד למקסימום. יש לנו גם תהליך של לחשב, כמה מקסימום פעמים נוכל לבצע הגדלה כפולה של שני
ערכים בבת אחת. ומכאן נובעת רמת הקושי הבאה של השאלה, שהיא, שיש לנו עוד חישוב אפשרי, לחשב, במידה ונבצע X הגדלות כפולות, ... MAX. ויש לנו עמודה אחת או יותר של הערך MIN. ויש לנו את כל שאר העמודות שבאמצע. לדוגמה (1,2,3,4,5,6,7,8,9,10) הערך MAX הוא 10. הערך MIN הוא 1. וכל השאר הם
ערכים שנמצאים בין ה MAX לבין הערך MIN. אז לצורך העניין ניקח את המטריצה שלנו ונסתכל עליה בצורה הבאה. נאתר את הערך MAX ... MAX הוא 10. זה בעצם אומר שאנחנו צריכים לבצע 9 פעולות הגדלה, על 1 כדי להביא אותו לערך 10. עכשיו נצטרך לספור את כמות פעולות ההגדלה שעלינו לבצע, על כל שאר
הערכים שאינם MAX ושאינם העמודה הבודדת של MIN שהגדרנו קודם. לדוגמה במקרה של (1,2,3,4,5,6,7,8,9,10) יש לנו MAX שהוא 10 יש לנו MIN שהוא 1 שצריכים לבצע עליו 9 הגדלות ויש לנו את שאר
הערכים (2,3,4,5,6,7,8) דהיינו, 7
ערכים שצריכים לגדול ל 10. דהיינו, הם צריכים להיות 710=70. ומאחר ש 2+3+4+5+6+7+8 = 35. אז 70-35 = 35. דהיינו, אנחנו ... ה 70. דהיינו, יש את הערך MAX שהוא כבר בערך המקסימאלי שלו. יש עמודה אחת של הערך MIN, שהיא צריכה לגדול ב MAX -MIN פעמים כדי להיות בערך MAX. ויש את כל שאר
הערכים, שהכמות שלהם כפול MAX פחות הסכום שלהם, שווה לכמות ההגדלות שאנחנו צריכים לבצע עליהם. בדוגמה הנל, כמות
הערכים היא 7, כפול MAX שהוא 10, פחות הסכום שלהם שהוא 35, יוצא 35 שזאת כמות ההגדלות שצריכים לבצע. ועכשיו נראה ... 3 מצבים אפשריים בלבד: אפשרות 1 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת זהה לכמות ההגדלות שאנחנו צריכים לבצע על כל שאר
ערכי הביניים, כדי להביא אותם לערך MAX. לדוגמה: אפשרות 2 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת גדולה מכמות ההגדלות שאנחנו צריכים לבצע על כל שאר
ערכי הביניים, כדי להביא אותם לערך MAX, שעליהם צריכים לבצע כמות הגדלות קטנה יותר. אפשרות 3 - שכמות ההגדלות שאנחנו צריכים לבצע על MIN כדי להביא אותו ל MAX, הכמות הזאת קטנה מכמות ההגדלות שאנחנו צריכים לבצע על כל שאר
ערכי הביניים, כדי להביא אותם לערך MAX, שעליהם צריכים לבצע כמות הגדלות גדולה יותר. לדוגמה: ואם נחקור את החוקיות של 3 המצבים האלו, נגלה את החוקיות הבאה: אפשרות 1 - אם כמות ההגדלות שאנחנו צריכים לבצע, כדי להביא את MIN ל MAX, היא זהה לכמות ההגדלות האחרות של כל
ערכי הביניים, הרי שכמות ההגדלות הכפולות שניתן יהיה לבצע, תהיה הכמות הכללית של ההגדלות שצריכים לבצע, לחלק ל 2. או במילים ...