אלגוריתמיקה - מציאת סכום האיברים הנותן תוצאה הכי קרובה למספר?

[intercooler3819]

שי - בלי לקרוא הכל יש פה כבר משהו מוזר
כתבת:

נכתב במקור על ידי Shay Falador

כתבתי פתרון שהסיבוכיות שלו היא בין n^2 - n (יותר קרוב לזה) לבין 2n - 2 (במקרים קיצוניים בלבד). return $data;
}[/PHP]

כשמדברים על סיבוכיות אפשר לדבר יותר על סדר גודל... הסדר גודל של סיבוכיות n^2-n הוא n^2 והסיבוכיות של 2n-2 הוא n... אפשר לראות בקלות שהסיבוכיות הראשונה הרבה יותר מסובכת מהשניה... מפה אני מנסה להבין איך המצב השני הוא המצב הקיצוני?! (אולי התבלבלת אני מניח, שוב - לא עברתי על הקוד)

בנוגע לפותח ההודעה

יש לי בראש פתרון אבל הוא לא פתרון יעיל...
בגדול לדעתי צריך לעשות דבר כזה...
צריך לקלוט את המספר ואת המספרים שאיתם צריך לבצע את הפעולות ואז לחלק אותם לקבוצות
לפי מה נחלק לקבוצות? לפי 3 תנאים מרכזיים:
תנאי ראשון להמשך באלגוריתם הוא שסכום כל הערכים המוחלטים של המספרים המוזנים גדול מהמספר אליו אנחנו שואפים (אם הוא שווה נחזיר את הסכום)

תנאי ראשון של החלוקה, כמות המספרים המקס' בכל קבוצה צריך להיות פרופורציוני לשורש של המספר שאנחנו רוצים להגיע אליו (אני חושב השורש כפול 1 זה סקאלה סבירה), כמות הקבוצות צריכה להיות גם בערך 1.5 כפול השורש של המספר אליו נרצה להגיע

החלוקה צריכה להיות לפי הקרבה של מספרים אחד לשני.. כלומר כל המספרים שקרובים אחד לשני והמקסימלי בקבוצה פחות המינימאלי בקבוצה לא יותר גדולים מהשורש של המספר כפול 2 בערך..
כשאני אומר קרבה משמע המספרים נמצאים קרוב על הציר
לפי מה שכתבתי עד כה אם נחלק את המספרים הבאים:
1 2 3 4 6 7 8 45 52 60
נקבל את הקבוצות הבאות:
1 2 3 4 6 7 8
45 52
60
בהנחה שהמספר אליו אנחנו שואפים הוא 100 (השורש שלו הוא 10)

מכאן אחרי החלוקה לקבוצות כדי להפעיל השוואה יעילה נמצא את המספר האמצעי בערך בכל קבוצה (לא ממוצע! אמצעי!) ונגיע למספרים הבאים:
4
45
60

לאחר מכן נבחן את כל האפשרויות של חיבורים/חיסורים בין ה"ראשי קבוצות", את האפשרויות נדרג בטבלה לפי הקרבה שלהם למספר המקורי (100) ונקבל שבראש הטבלה שלנו יש את
60+45 = 105
כעת אנחנו רואים כי עברנו את המספר, נמשיך לרדת עד שנמצא מספר מדויק

אם נראה שאנחנו יוצאים מהטווח שבו ההפרש בין הפתרונות קטן משורש של הפתרון כפול 2 אז נעזוב את הנוסחא הנוכחית ונעבור לבאה בתור בטבלה שלנו ופשוט נשבץ אליה את המספרים
ככל שיש יותר מספרים ככה הסיבוכיות גדלה.. מה גם שיש פה הרבה פרמטרים שצריך לחשוב עליהם והרבה בדיקות שיש לעשות

בסופו של דבר אני חושב שזה יותר יעיל מלבדוק את כל הפתרונות האפשריים, אבל עדיין לא מספיק יעיל


שאלה אחרונה - למה אתה צריך את הדבר הזה?? אם תתן כיוון אולי אפשר לפתור את זה בדרך אחרת

[Shay Ben Moshe]

ניצן דבר ראשון אני שמח שהגבת למה שכתבתי, אין לי כוח לקרוא את כל התגובה שלך אבל לגבי מה שכתבת לי ככה:
אני לא מבין יותר מדי בעניין של סיבוכיות, אני בא מתחום של מתמטיקה, לוקח מונחים ומנסה לחבר אותם עד כמה שאני מבין. אז רק שאני אבין, אין חשיבות למעשה למקדמים? (משמע שבביטוי ax^y אין חשיבות לa)
בנוסף, מכיוון שהפתרון שלי שם עובד על תנאי כלשהו אז הוא יכול לקצר את הפתרון, אבל לא הייתי מסתמך על זה כיוון שזה יקרה רק בחלק מהמקרים, תלוי בקלט.

שוב תודה.

[intercooler3819]

נכתב במקור על ידי Shay Falador

ניצן דבר ראשון אני שמח שהגבת למה שכתבתי, אין לי כוח לקרוא את כל התגובה שלך אבל לגבי מה שכתבת לי ככה:
אני לא מבין יותר מדי בעניין של סיבוכיות, אני בא מתחום של מתמטיקה, לוקח מונחים ומנסה לחבר אותם עד כמה שאני מבין. אז רק שאני אבין, אין חשיבות למעשה למקדמים? (משמע שבביטוי ax^y אין חשיבות לa)
בנוסף, מכיוון שהפתרון שלי שם עובד על תנאי כלשהו אז הוא יכול לקצר את הפתרון, אבל לא הייתי מסתמך על זה כיוון שזה יקרה רק בחלק מהמקרים, תלוי בקלט.

שוב תודה.

ממ יש חשיבות מסוימת זה מאוד תלוי בביטוי אבל בגדול לרוב כשמדברים על סיבוכיות אפשר לדבר על סדרי גודל
קח תראה את זה אולי זה יעשה לך סדר בראש
http://www.youtube.com/watch?v=A2cmlhfdxuY

כשאתה עובד עם N^2 גם אם תוריד ממנו 8 או תוריד ממנו N זה לא יעשה הבדל רציני בסיבוכיות שתשאר בערך N^2
אם תעבוד עם N ותוסיף לו N עדיין בדרך כלל הסדר גודל ישאר אותו דבר.. לכן הסיבוכיות אפשר לקרב אותה ל N

זה לא בדיוק מדע מדויק... אז אל תתפוס אותי על קטנות (את האמת זה כן חח)