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

[Shay Ben Moshe]

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

PHP קוד:

<?php

function find($array, $target) {
    if(count($array) < 2)
        return false;
    sort($array);
    $data = array(
        'diff'    => $target - $array[0] - $array[1],
        'arg1'    => 0,
        'arg2'    => 1,
        'opt'    => '+'
    );
    for($i = 0; $i < count($array); $i++) {
        $last_diff = null;
        for($j = $i + 1; $j < count($array); $j++) {
            $diff = abs($target - $array[$i] - $array[$j]);
            if(!is_null($last_diff) && $diff > $last_diff)
                break;
            if($diff < $data['diff']) {
                $data['opt'] = '+';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = $diff;
            }
            $last_diff = $diff;
        }
    }
    for($i = count($array) - 1; $i > 0; $i--) {
        $last_diff = null;
        for($j = $i - 1; $j >= 0; $j--) {
            $diff = abs($target - $array[$i] + $array[$j]);
            if(!is_null($last_diff) && $diff > $last_diff)
                break;
            if($diff < $data['diff']) {
                $data['opt'] = '-';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = $diff;
            }
            $last_diff = $diff;
        }
    }
    return $data;
}

נריץ:

PHP קוד:

print_r(find(array(10, 40, 70), 58)); 


הפלט:

PHP קוד:

Array
(
    [diff] => 2
    [arg1] => 2
    [arg2] => 0
    [opt] => -
) 


הצעות ליעול יתקבלו בברכה. (וכשכתבתי את זה בשעה כזו אני בטוח שתיהינה)

עריכה:
הפתרון בלי הוידוי של ההפרש (השוותי אותם, עם הוידוי יותר מהיר בגדול, ככל שיש יותר "מיותרים" ככה הוא יותר יעיל מן הסתם):

PHP קוד:

<?php

function find($array, $target) {
    if(count($array) < 2)
        return false;
    sort($array);
    $data = array(
        'diff'    => $target - $array[0] - $array[1],
        'arg1'    => 0,
        'arg2'    => 1,
        'opt'    => '+'
    );
    for($i = 0; $i < count($array); $i++) {
        for($j = $i + 1; $j < count($array); $j++) {
            if(abs($target - $array[$i] - $array[$j]) < $data['diff']) {
                $data['opt'] = '+';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = abs($target - $array[$i] - $array[$j]);
            }
        }
    }
    for($i = count($array) - 1; $i > 0; $i--) {
        for($j = $i - 1; $j >= 0; $j--) {
            if(abs($target - $array[$i] + $array[$j]) < $data['diff']) {
                $data['opt'] = '-';
                $data['arg1'] = $i;
                $data['arg2'] = $j;
                $data['diff'] = abs($target - $array[$i] + $array[$j]);
            }
        }
    }
    return $data;
}

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

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


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