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