שי - בלי לקרוא הכל יש פה כבר משהו מוזר
כתבת:
ציטוט:
נכתב במקור על ידי 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 אז נעזוב את הנוסחא הנוכחית ונעבור לבאה בתור בטבלה שלנו ופשוט נשבץ אליה את המספרים
ככל שיש יותר מספרים ככה הסיבוכיות גדלה.. מה גם שיש פה הרבה פרמטרים שצריך לחשוב עליהם והרבה בדיקות שיש לעשות
בסופו של דבר אני חושב שזה יותר יעיל מלבדוק את כל הפתרונות האפשריים, אבל עדיין לא מספיק יעיל
שאלה אחרונה - למה אתה צריך את הדבר הזה?? אם תתן כיוון אולי אפשר לפתור את זה בדרך אחרת