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

[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;
}