חיבור בינארי של M מספרים

[janemayers]

חיבור בינארי של M מספרים

מייצגים מונה בייצוג בינארי, בתור רשימה מקושרת של ביטים, מהביט הפחות סיגניפיקנטי לביט הסיגניפיקנטי ביותר. למשל, המספר 5 ייצוג ע"י הרשימה 1->0->1 הפעולה PLUS(N) מקבלת מספר טבעי N, שמיוצג אף הוא ע"י רשימת ביטים,כנ"ל, ומגדילה את המונה ב-N. ממש את הפעולה ומצא את זמן הריצה של M פעולות. הערה: בכל אחת מ-M הפעולות אפשר לבחור N שונה כרצוננו. האלגוריתם שחשבתי עליו הוא לעבור על שתי הרשימות במקביל עד שאחת מהן נגמרת, ולעדכן את המונה לפי הצורך (כששומרים תמיד עוד ביט זיכרון שנגרר הלאה לפעולת החיבור הבאה). כשאחת הרשימות נגמרת ממשיכים עם השנייה ובסוף - כשתתיהן נגמרו - מקסימום מוסיפים עוד איבר עם 1 אם ביט הזיכרון אינו מאופס. 1. האם נשמע לכם נכון? 2. יש לי קושי בניתוח זמן הריצה...

 

[freak2100]

כן

בעקרון מבצעים בעצם "חיבור ארוך", ז"א מספרת ה"אחדות" ומעלה, כל פעם מחברים את שני הביטים ושומרים את הcarry out (אם אני זוכר נכון את שמו) לשני הביטים הבאים. רק לגבי תנאי העצירה - צריך להמשיך לרוץ עד שהמספר N נגמר והcarry out מתאפס. אם המספר השני נגמר והcarry out התאפס, אין כבר מה להוסיף למונה. אם הגענו לסוף המונה ועוד לא הגענו לסוף המספר שמחברים אליו, או אם יש carry out, צריך להמשיך (ולשרשר למונה עוד ביטים לפי הצורך). האלגוריתם הזה עובר בסך הכל על הרשימה השנייה (M), או עד שהcarry out מתאפס, המאוחר מבינהם. אם הוא עובר רק על M אז זה כמובן O של |M| (כש|M| = מספר הביטים בM). אם הcarry out לא מתאפס בסוף הריצה הראשונה, זה אומר ש|N|>|M|, והריצה תסתיים במקרה הגרוע ביותר כשנגיע לתא אחד אחרי התא האחרון בN. ככה שבסך הכל זה:

O(max{|M|, |N|})​