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