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