Как улучшить этот алгоритм для повышения эффективности во время выполнения?

У меня недавно было задание в моем классе алгоритмов. Постановка задачи приведена ниже:

Напишите и кратко объясните следующую функцию C ++: int Sum (int *nums, int len); которая принимает массив целых чисел, nums, содержащий len> 0 натуральных чисел и возвращает сумму, ближайшую к 330, которая была найдена путем добавления до трех целых чисел в массиве (где каждый элемент массива может быть включен только один раз в сумму) ,
Например, если [nums] содержит [10 100 200 2] и len == 4, функция возвращает
310 = 200 + 100 + 10. Если [nums] содержит [10 100 230 2] и len == 4, функция возвращает 330 = 100 + 230.

Моя попытка кода:

#include <iostream>
#include <limits.h>
#include <cmath>
#include <climits>
using namespace std;

/*
* Description: function to find the sum closed to 330 by adding up
*              to 3 integers
* Arguments  : nums - integer array
*              len  - length of integer array
* Return     : sum closest to 330
*/
int Sum (int *nums, int len)
{
const int number = 330;
/* variable to store sum closest to 330 */
int closest_sum = 0;
/* variable to store difference of sum from 330 */
int diff = INT_MAX;
/* iterate over the integer array to find the sum closest to 330 */
for(int i = 0; i < len; i++)
{
/* temporary variable to hold sum of integers */
int sum = 0;
/* set first of 3 numbers as the sum */
sum = nums[i];
/* if the first number is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with previous */
/* difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous difference, */
/* update diff and set closest sum to current sum */
diff = abs(number - sum);
closest_sum = sum;
}
/* include the second of 3 numbers */
for(int j = i + 1; j < len; j++)
{
/* set sum as the addition of the first 2 numbers */
sum = nums[i] + nums[j];
/* if the sum is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with previous */
/* difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous difference, */
/* update diff and set closest sum to current sum */
diff = abs(number - sum);
closest_sum = sum;
}
/* include the third of 3 numbers */
for(int k = j + 1; k < len; k++)
{
/* set sum as the addition of the 3 numbers */
sum = nums[i] + nums[j] + nums[k];
/* if the sum is equal to 330, no need to move forward; */
/* return 330 */
if(abs(number - sum) == 0) return number;
/* compare the absolute difference of sum and 330 with */
/* previous difference */
if(abs(number - sum) < diff)
{
/* if current difference is less than previous */
/* difference, update diff and set closest sum to current */
/* sum */
diff = abs(number - sum);
closest_sum = sum;
}
}
}
}
/* return closest sum to 330 */
return closest_sum;
}

int main() {
const int len = 6;
int arr[len] = {300, 320, 310, 500, 5, 330};
cout << "Closest to 330:\t" << Sum(arr, len) << endl;
return 0;
}

Код работает правильно и прошел все тестовые случаи, которые использовал грейдер. Тем не менее, часть оценки были связаны с эффективностью кода. Я потерял очки, потому что время выполнения кода ϴ (n ^ 3) (из-за трех вложенных for петли).

Мой вопрос: как можно улучшить этот алгоритм, чтобы он был более эффективным, то есть с временем выполнения менее ϴ (n ^ 3)?

РЕДАКТИРОВАТЬ: Просто чтобы прояснить, до того времени, когда это назначение было назначено, мы изучали только массивы / векторы, асимптотические обозначения, время рекурсии / повторения в классе. Я почти уверен, что мы не должны были использовать кучи, бинарный поиск (который, на самом деле, мы будем изучать на следующей неделе), алгоритмы сортировки и т. Д. Также, пожалуйста, обратите внимание, что вопрос говорит до трех целых, то есть ближайшая к 330 сумма может состоять из 1 цифры, 2 цифр или 3 цифр. Я должен принять во внимание все эти возможности.

-2

Решение

Если вы сначала отсортируете свои числа, у вас может быть вложенный цикл, который проверяет каждую пару чисел и выбирает третье число с помощью двоичного поиска.

сложность этого алгоритма составляет O (N ^ 2 * log (N)), (плюс N log (N) для сортировки)

2

Другие решения

Я подозреваю, что ваш инструктор может подумать о неправильно ответ.

Вы можете использовать два цикла для генерации вектора всех парных сумм, а затем использовать еще два цикла, чтобы добавить к ним третье число. Это «избегает» третьего уровня вложенности.

Этот ответ неправильно, однако, потому что длина сгенерированного вектора O (N ^ 2). Это дает вам петлю O (N) внутри петли O (N ^ 2), делая сложность двух петель, объединенных O (N ^ 3)

Основная причина вашей проблемы заключается в том, что действительно существует N ^ 3 возможных сумм. Даже если принять во внимание 3! В разных порядках, в которых можно добавить три числа, любое решение, учитывающее все возможные триплеты, должно быть O (N ^ 3). Любое лучшее решение должно пропустить некоторые суммы сразу. Существующий ответ Себастьяна пропускает некоторые из этих сумм, сортируя входные данные, поэтому вы можете исключить большой набор возможностей с помощью бинарного поиска в журнале (N). Но с простым обычным вектором вы не можете пропустить любой ввод.

Есть несколько трюков, которые улучшат ожидаемый время выполнения, но только по константе. Например, вы можете рассчитать минимальное и максимальное значение входа в O (N). Затем вы можете упростить задачу, вычтя минимум из всех входных данных и 3 * минимум из целевого значения. Проблема [10 100 200 2] => 330 упрощает до [8 98 198 0] = > 324, Преимущество наличия максимума в том, что вы можете пропустить внутренний цикл для немного пар. После добавления 8+0Понятно что даже добавив максимум 198 только даст вам 206, что будет хуже, чем лучший результат, который вы получите в этот момент.

0

По вопросам рекламы [email protected]