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