Минимальная сумма сумм в С

Question

Вот краткий обзор проблемы:

Нам дан массив int.Нам нужно сжать массив в одно целое.Каждое сжатие добавляет два целых числа вместе.Значение, возвращаемое из сжатия, возвращается в группу «необходимо сжать» и добавляется к промежуточной сумме для всех сжатий.Таким образом, цель состоит в том, чтобы получить минимальную сумму, когда массив полностью сжат.Вот пример, если я не имею смысла:

————

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 9 = 14.         0+14 = 14
[14, 12, 15] -> 14 + 12 = 26.        14+26 = 40
[26, 15] -> 26 + 15 = 41.            40+41 = 81
[41] -> Done 

Так что здесь 81 - решение.

————

И только для полноты.Вот неправильное решение:

To Be Compressed                Runningsum   sum
[5, 12, 9, 15] -> 5 + 12 = 17.        0+17 = 17
[17, 9, 15] -> 9 + 15 = 24.          17+24 = 41
[17, 24] -> 17 + 24 = 41.            41+41 = 82
[41] -> Done

Так что здесь 82 не является оптимальной суммой.

————

Я понимаю, как сделать эту грубую силу O (n ^ 2), выполнив двойной цикл for и найдя следующий минимум в массиве каждого внутреннего цикла.Затем во внешнем цикле текущая сумма устанавливается на себя + только что найденная минимальная сумма, а затем текущая сумма добавляется к общей сумме.

    findminimum() //5
runningsum=runningsum + 5
sum=0
    findminimum() //9
runningsum=runningsum + 9  //5+9=14
sum+=runningsum            //0+14=14
    findminimum() //12
runningsum=runningsum + 12 //14+12=26
sum+=runningsum            //14+26=40
    findminimum() //15
runningsum=runningsum + 15 //26+15=41
sum+=runningsum            //40+41=81

return sum

Это работает, но, очевидно, O (n ^ 2) нелучшее.

Далее вы можете объединить массив.Так как массив отсортирован, нам не нужно было бы делать второй цикл for, который находил следующую мину, как findminimum () выше.Таким образом, мы можем просто выполнить runningsum и суммировать математику в одном цикле for.Это будет O (nlog (n)).

Итак, мой вопрос, вы все видите какой-либо способ сделать это в O (n) или nlogn кажется наилучшей возможностью?Для решения этой проблемы может быть использована математическая формула, с которой я просто не знаком.

Если что-то неясно, я рад уточнить.Спасибо за ваше время!

Answer 1

Я думаю, что вашего оптимизированного подхода недостаточно. Представьте себе следующий вход:

[4, 5, 7, 8, 10]

В этом случае у вас уже есть заказанный список. Предположим также, что оно реализовано в виде двоичного дерева, поэтому поиск выполняется за O (log (n)).

Теперь вы добавляете 4 и 5. Результат 9 не является операндом следующей операции суммирования. Таким образом, вы должны вставить его в отсортированный список, который является O (log (n)).

Поэтому даже с уже отсортированным списком у вас есть O (n * log (n)).

Таким образом, причина, по которой вы не можете достичь сложности O (log (n)), заключается в том, что ваша сумма n зависит от суммы n - 1 и упорядочения этого результата в остальных ваших входных данных. Поэтому подход добавления n * a [0] + (n - 1) * a [1] ... не может быть успешным.

Answer 2

Если ваше минимальное время выполнения действительно связано с вашим типом сортировки, тогда классическая сортировка сравнения даст вам наилучшую оценку O (nlogn).

По ключевому слову есть сортировка "сравнение".

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

Эта ссылка описывает, например, то, что называется сортировкой подсчета.

Это (намного) лучше объясняет, чем то, что я могу сделать здесь. По сути, вы выделяете массив размером max (arrtoMinSum), затем для каждого элемента в arrToMinSum вы увеличиваете значение массива по этому индексу. После накопления суммы в этом выделенном массиве вы затем выполняете итерацию по своему исходному массиву и используете значения в выделенном массиве в качестве индексов для хранения каждого из значений в исходном массиве в конечном выходном массиве. Я настоятельно рекомендую вам прочитать его, а не осуществлять на основе моего объяснения.

Поскольку вы создаете массив с максимальным размером (arrToMinSum) и перебираете его и свой исходный массив, время выполнения будет O(max(max(arrToMinSum),n). Это (во многих большинстве случаев) быстрее, чем сортировка сравнения, за счет более высокого использования памяти.