Самый быстрый алгоритм, чтобы взять произведение всех подмножеств

23

Учитывая nчисла в массиве (вы не можете предполагать, что они являются целыми числами), я хотел бы вычислить произведение всех подмножеств размера n-1.

Вы можете сделать это, умножив все числа вместе, а затем разделив их по очереди, пока ни одно из чисел не будет равно нулю. Однако как быстро вы можете сделать это без деления?

Если вы не разрешаете деление, какое минимальное количество арифметических операций (например, умножение и сложение) необходимо для вычисления произведения всех подмножеств размера n-1?

Очевидно, вы можете сделать это в (n-1)*nумножении.

Для пояснения, выходные данные - это nразные продукты, и единственными операциями, кроме чтения и записи в память, являются умножение, сложение и вычитание.

пример

Если на входе три числа 2,3,5, то на выходе три числа 15 = 3*5, 10 = 2*5и 6 = 2*3.

Критерий победы

Ответы должны дать точную формулу для числа арифметических операций, которые их код будет использовать в терминах n. Чтобы упростить жизнь, я просто подключусь n = 1000к вашей формуле, чтобы оценить ее результат. Чем ниже, тем лучше.

Если слишком сложно создать точную формулу для вашего кода, вы можете просто запустить ее n = 1000и подсчитать арифметические операции в коде. Точная формула будет лучше, однако.

Вы должны добавить свою оценку для n=1000вашего ответа для легкого сравнения.

Артур
источник
4
Можем ли мы считать умножение на 1 бесплатным? В противном случае я бы определил функцию пользовательского умножения, которая делает это.
xnor
3
Было бы противно делать параллельное умножение целой связки путем объединения чисел с достаточным количеством разделительных цифр 0?
xnor
1
Считаются ли такие операции, как +на индексах ? Если это так, учитывается ли индексирование массива? (поскольку это все-таки синтаксический сахар для добавления и разыменования).
Nore
2
@nore Хорошо, я сдаюсь :) Просто посчитай арифметические операции, которые каким-то образом связаны с вводом.
Артур
1
Очевидно , вы можете сделать это в (n-1)*nумножениях Вы имеете в виду (n-2)*n, не так ли?
Луис Мендо

Ответы:

25

Python, 3 (n-2) операции, оценка = 2994

l = list(map(float, input().split()))
n = len(l)

left = [0] * len(l)
right = [0] * len(l)
left[0] = l[0]
right[-1] = l[-1]
for i in range(1,len(l)-1):
  left[i] = l[i] * left[i - 1]
  right[-i-1] = l[-i-1] * right[-i]

result = [0] * len(l)
result[-1] = left[-2]
result[0] = right[1]
for i in range(1, len(l) - 1):
  result[i] = left[i - 1] * right[i+1]

print(result)

Массивы leftи rightсодержат накопленные произведения массива слева и справа соответственно.

РЕДАКТИРОВАТЬ: Доказательство того, что 3 (n-2) является оптимальным количеством операций, необходимых для n> = 2, если мы используем только умножение.

Мы сделаем это по индукции; с помощью приведенного выше алгоритма нам просто нужно доказать, что при n> = 2 3 (n-2) является нижней границей количества необходимых умножений.

Для n = 2 нам нужно как минимум 0 = 3 (2-2) умножения, поэтому результат тривиален.

Пусть n> 2, и предположим, что для n - 1 элементов нам нужно как минимум 3 (n-3) умножения. Рассмотрим решение для n элементов с k умножениями. Теперь мы удалим последний из этих элементов, как если бы он был 1, и упростим все умножения непосредственно на него. Мы также убираем умножение, приводящее к произведению всех других элементов, так как оно не требуется, поскольку его никогда нельзя использовать в качестве промежуточного значения для получения произведения n-2 других элементов, поскольку деление не допускается. Это оставляет нам с умножением l и решением для n - 1 элементов.

По предположению индукции l> = 3 (n-3).

Теперь давайте посмотрим, сколько умножений было удалено. Одним из них был тот, который приводил к произведению всех элементов, кроме последнего. Кроме того, последний элемент использовался непосредственно по крайней мере в двух умножениях: если он использовался только в одном, то он использовался при умножении на промежуточный результат, состоящий в некотором произведении других элементов; скажем, без потери общности, этот промежуточный результат включил первый элемент в продукт. Тогда нет способа получить произведение всех элементов, кроме первого, поскольку каждый товар, который содержит последний элемент, является либо последним элементом, либо содержит первый элемент.

Таким образом, k> = l + 3> = 3 (n-2), что доказывает утверждение теоремы.

Нора
источник
8
Оказывается , это очень чистый в Haskell : f l = zipWith (*) (scanl (*) 1 l) (scanr (*) 1 $ tail l).
xnor
Комментарии не для расширенного обсуждения; этот разговор был перенесен в чат .
Деннис
12

Хаскелл , оценка 2994

group :: Num a => [a] -> [[a]]
group (a:b:t) = [a,b] : group t
group [a] = [[a]]
group [] = []

(%) :: (Num a, Eq a) => a -> a -> a
a % 1 = a
1 % b = b
a % b = a * b

prod_one_or_two :: (Num a, Eq a) => [a] -> a
prod_one_or_two [a, b] = a % b
prod_one_or_two [x] = x

insert_new_value :: (Num a, Eq a) => ([a], a) -> [a]
insert_new_value ([a, b], c) = [c % b, c % a]
insert_new_value ([x], c) = [c]

products_but_one :: (Num a, Eq a) => [a] -> [a]
products_but_one [a] = [1]
products_but_one l = 
    do combination <- combinations ; insert_new_value combination
    where 
        pairs = group l
        subresults = products_but_one $ map prod_one_or_two pairs
        combinations = zip pairs subresults

Попробуйте онлайн!

Скажем, нам дали список [a,b,c,d,e,f,g,h]. Сначала мы сгруппируем его в пары [[a,b],[c,d],[e,f],[g,h]]. Затем мы возвращаемся к списку половинных размеров pairsих продуктов, чтобы получитьsubresults

[a*b, c*d, e*f, g*h] -> [(c*d)*(e*f)*(g*h), (a*b)*(e*f)*(g*h), (a*b)*(c*d)*(g*h), (a*b)*(c*d)*(e*f)]

Если мы возьмем первый элемент (c*d)*(e*f)*(g*h)и умножим его на bи aсоответственно, мы получим произведение всех, кроме aи всех, кроме b. Делая это для каждой пары и получая рекурсивный результат при отсутствии этой пары, мы получим окончательный результат. Случай нечетной длины специально обрабатывается тем, что нечетный элемент передается непарным на рекурсивный шаг, а произведение оставшихся возвращаемых элементов является произведением без него.

Количество умножений t(n)является n/2для продукта сопряжения, t(n/2)для рекурсивного вызова, а другое nдля продуктов с отдельными элементами. Это дает t(n) = 1.5 * n + t(n/2)за странность n. Использование более точных подсчетов для нечетного nи игнорирование умножения с 1для базового случая дает оценку 2997для n=1000.

XNOR
источник
Это очень мило.
Артур
Я думаю, что причина, по которой оценка составляет 2995, а не 2994, как в моем ответе, заключается в том, что она вычисляет произведение всех чисел и в степени не двух, которая позже усекается. Возможно, осторожная обработка products_but_one'может избежать этого, возвращая что-то правильной длины.
Nore
@nore Я обнаружил, что у меня было дополнительное умножение в моем счетчике, потому что я забыл, что в базовом случае есть 1свободное умножение. Я думаю, что отступ 1 не влияет на вещи, но я очистил свой алгоритм, чтобы не использовать их.
xnor
Предполагает ли этот код, что входные данные являются целыми числами?
@Lembik Да, но только в необязательных аннотациях типов. Я изменю их всех на float.
xnor
9

Haskell , оценка 9974

partition :: [Float] -> ([Float], [Float])
partition = foldr (\a (l1,l2) -> (l2, a:l1)) ([],[])

(%) :: Float -> Float -> Float
a % 1 = a
1 % b = b
a % b = a*b

merge :: (Float, [Float]) -> (Float, [Float]) -> (Float, [Float])
merge (p1,r1) (p2, r2) = (p1%p2, map(%p1)r2 ++ map(%p2)r1)

missing_products' :: [Float] -> (Float, [Float])
missing_products' [a] = (a,[1])
missing_products' l = merge res1 res2
    where
        (l1, l2) = partition l
        res1 = missing_products' l1
        res2 = missing_products' l2

missing_products :: [Float] -> [Float]
missing_products = snd . missing_products'

Попробуйте онлайн!

Стратегия «разделяй и властвуй», очень напоминающая сортировку слиянием. Не выполняет индексацию.

Функция partitionразбивает список на равные по возможности половины, помещая чередующиеся элементы на противоположных сторонах раздела. Мы рекурсивно объединяем результаты (p,r)для каждой из половин со rсписком продуктов с одним отсутствующим и pобщим продуктом.

Для вывода полного списка отсутствующий элемент должен находиться в одной из половин. Продукт с отсутствующим элементом - это один отсутствующий продукт для половины, в которой он находится, умноженный на полный продукт для другой половины. Итак, мы умножаем каждый продукт с одним отсутствующим на полный продукт другой половины и составляем список результатов, как map(*p1)r2 ++ map(*p2)r1). Это требует nумножения, где nдлина. Нам также нужно сделать новый полный продукт p1*p2для будущего использования, что обойдется еще в 1 умножение.

Это дает общую рекурсию для ряда операций t(n)с nчетным: t(n) = n + 1 + 2 * t(n/2). Нечетный похож, но один из подсписков 1больше. Выполняя рекурсию, мы получаем n*(log_2(n) + 1)умножения, хотя различие нечетное / четное влияет на это точное значение. Значения до t(3)улучшаются не умножением 1, определив вариант (%)из того, (*)что ярлыки _*1или 1*_случаев.

Это дает 9975умножения для n=1000. Я считаю, что лень Хаскелла означает, что неиспользованный общий продукт во внешнем слое не рассчитывается 9974; если я ошибаюсь, я мог бы опустить это явно.

XNOR
источник
Ты избил меня по отметке времени на минуту раньше.
Nore
Если трудно точно сформулировать формулу, просто запустите ее n = 1000и посчитайте арифметические операции в коде.
Артур
Поскольку наш код в основном один и тот же, я не понимаю, как вы к ним привыкли, 9974а не к 9975умножениям n = 1000(в случае вычисления общего продукта во внешнем слое). Включили ли вы 1во вход, который вы использовали для проверки?
Nore
@nore Ты прав, я был один. Я написал код для выполнения рекурсии по числу вызовов функции умножения. Подсчет звонков напрямую будет более надежным - кто-нибудь знает, как я это сделаю в Haskell?
xnor
1
@xnor вы можете использовать traceиз Debug.Traceс броским все | trace "call!" False = undefinedнастороже, я думаю. Но это используется unsafePerformIOпод капотом, так что это не так уж и много улучшений.
Сохам Чоудхури
6

Хаскелл , оценка 2994

group :: [a] -> Either [(a, a)] (a, [(a, a)])
group [] = Left []
group (a : l) = case group l of
  Left pairs -> Right (a, pairs)
  Right (b, pairs) -> Left ((a, b) : pairs)

products_but_one :: Num a => [a] -> [a]
products_but_one [_] = [1]
products_but_one [a, b] = [b, a]
products_but_one l = case group l of
  Left pairs ->
    let subresults =
          products_but_one [a * b | (a, b) <- pairs]
    in do ((a, b), c) <- zip pairs subresults; [c * b, c * a]
  Right (extra, pairs) ->
    let subresult : subresults =
          products_but_one (extra : [a * b | (a, b) <- pairs])
    in subresult : do ((a, b), c) <- zip pairs subresults; [c * b, c * a]

Попробуйте онлайн!

Как это работает

Это очищенная версия алгоритма xnor, которая упрощает нечетный случай более простым способом (правка: похоже, xnor очистил его таким же образом):

[a, b, c, d, e, f, g] ↦
[a, bc, de, fg] ↦
[(bc) (de) (fg), a (de) (fg), a (bc) ( fg), a (bc) (de)] по рекурсии ↦
[(bc) (de) (fg), a (de) (fg) c, a (de) (fg) b, a (bc) (fg) e, a (bc) (fg) d, a (bc) (de) g, a (bc) (de) f]

[a, b, c, d, e, f, g, h] ↦
[ab, cd, ef, gh] ↦
[(cd) (ef) (gh), (ab) (ef) (gh), ( ab) (cd) (gh), (ab) (cd) (ef)] путем рекурсии ↦
[(cd) (ef) (gh) b, (cd) (ef) (gh) a, (ab) (ef ) (gh) d, (ab) (ef) (gh) c, (ab) (cd) (gh) f, (ab) (cd) (gh) e, (ab) (cd) (ef) h, (аb) (CD) (EF) г].

Андерс Касеорг
источник
«Учитывая n чисел в массиве (вы не можете предполагать, что они являются целыми числами),« Мы не можем предполагать, что они являются целыми числами
5

O (n log n) операций, оценка = 9974

Работает с бинарным деревом.

питон

l = list(map(int, input().split()))
n = len(l)

p = [0] * n + l
for i in range(n - 1, 1, -1):
  p[i] = p[i + i] * p[i + i+1]

def mul(x, y):
  if y == None:
    return x
  return x * y

r = [None] * n + [[None]] * n
for i in range(n - 1, 0, -1):
  r[i] = [mul(p[i + i + 1], x) for x in r[i + i]] + [mul(p[i + i], x) for x in r[i + i + 1]]

u = r[1]
j = 1
while j <= n:
  j += j
print(u[n+n-j:] + u[:n+n-j])

Это также требует операций добавления списка и некоторой арифметики для чисел, которые не являются входными значениями; не уверен, что это считается. mulФункция есть , чтобы сохранить п операций для базового случая, чтобы не тратить их путем умножения на 1. В любом случае, это O (N журнал N) операций. Точная формула есть, если только подсчет арифметических операций над числами входных с j = floor(log_2(n)): j * (2^(j + 1) - n) + (j + 1) * (2 * n - 2^(j + 1)) - 2.

Спасибо @xnor за сохранение одной операции с идеей не вычислять внешний продукт!

Последняя часть - вывод продуктов в порядке пропущенного термина.

Нора
источник
Если трудно точно сформулировать формулу, просто запустите ее n = 1000и посчитайте арифметические операции в коде.
Артур
Я насчитал 10975 операций ...?
HyperNeutrino
p[i] = p[i + i] * p[i + i+1]не считается
HyperNeutrino
Речь идет об n log2 n + nоперациях (это O (nlogn) между прочим
HyperNeutrino
@HyperNeutrino операции p[i] = p[i + i] * p[i + i + 1]должны быть сохранены путем оптимизации умножения. Я мог бы посчитать слишком много, однако.
Nore
3

O ((n-2) * n) = O (n 2 ): тривиальное решение

Это просто тривиальное решение, которое умножает вместе каждое из подмножеств:

питон

def product(array): # Requires len(array) - 1 multiplication operations
    if not array: return 1
    result = array[0]
    for value in array[1:]:
        result *= value
    return result

def getSubsetProducts(array):
    products = []
    for index in range(len(array)): # calls product len(array) times, each time calling on an array of size len(array) - 1, which means len(array) - 2 multiplication operations called len(array) times
        products.append(product(array[:index] + array[index + 1:]))
    return products

Обратите внимание, что это также требует nопераций добавления списка; не уверен, что это считается. Если это не разрешено, то product(array[:index] + array[index + 1:])можно заменить на product(array[:index]) * product(array[index + 1:]), что изменяет формулу на O((n-1)*n).

HyperNeutrino
источник
Вы можете добавить свой собственный счет к ответу. 998 * 1000 в этом случае.
Артур
Не нуждается в вашей productфункции O(n)операций? по одному на каждый элемент в массиве (хотя это можно легко изменить O(n-1))
Roman Gräf
@ RomanGräf Правда. Я изменю это на O (n-1), но спасибо за указание на это.
HyperNeutrino
Это было изменено на атомный код-гольф ...
Эрик Outgolfer
@EriktheOutgolfer Что это делает мой счет сейчас? Если я не являюсь явно глупым, разве тег и спецификации не противоречат друг другу сейчас?
HyperNeutrino
3

Питон, 7540

Трехсторонняя стратегия слияния. Я думаю, что могу сделать даже лучше, чем это, с еще большим слиянием. Это O (n log n).

РЕДАКТИРОВАТЬ: Исправлена ​​ошибка.

count = 0
def prod(a, b):
    if a == 1: return b
    if b == 1: return a
    global count
    count += 1
    return a * b

def tri_merge(subs1, subs2, subs3):
    total1, missing1 = subs1
    total2, missing2 = subs2
    total3, missing3 = subs3

    prod12 = prod(total1, total2)
    prod13 = prod(total1, total3)
    prod23 = prod(total2, total3)

    new_missing1 = [prod(m1, prod23) for m1 in missing1]
    new_missing2 = [prod(m2, prod13) for m2 in missing2]
    new_missing3 = [prod(m3, prod12) for m3 in missing3]

    return prod(prod12, total3), new_missing1 + new_missing2 + new_missing3

def tri_partition(nums):
    split_size = len(nums) // 3
    a = nums[:split_size]
    second_split_length = split_size + (len(nums) % 3 == 2)
    b = nums[split_size:split_size + second_split_length]
    c = nums[split_size + second_split_length:]
    return a, b, c

def missing_products(nums):
    if len(nums) == 1: return nums[0], [1]
    if len(nums) == 0: return 1, []
    subs = [missing_products(part) for part in tri_partition(nums)]
    return tri_merge(*subs)

def verify(nums, res):
    actual_product = 1
    for num in nums:
        actual_product *= num
    actual_missing = [actual_product // num for num in nums]
    return actual_missing == res[1] and actual_product == res[0]

nums = range(2, int(input()) + 2)
res = missing_products(nums)

print("Verified?", verify(nums, res))
if max(res[1]) <= 10**10: print(res[1])

print(len(nums), count)

Соответствующая функция missing_products, которая дает общий продукт и все из них с отсутствующим элементом.

isaacg
источник
Вы посчитали умножения в tri_merge? Кроме того, вы можете заменить 2 * split_size + ...в tri_partitionс split_size + split_size + ....
Роман Греф
@ RomanGräf Я реструктурировал его согласно вашему предложению.
Исаак
1

DC, оценка 2994

#!/usr/bin/dc -f

# How it works:
# The required products are
#
#   (b × c × d × e × ... × x × y × z)
# (a) × (c × d × e × ... × x × y × z)
# (a × b) × (d × e × ... × x × y × z)
# ...
# (a × b × c × d × e × ... × x) × (z)
# (a × b × c × d × e × ... × x × y)
#
# We calculate each parenthesised term by
# multiplying the one above (on the left) or below
# (on the right), for 2(n-2) calculations, followed
# by the n-2 non-parenthesised multiplications
# giving a total of 3(n-2) operations.

# Read input from stdin
?

# We will store input values into stack 'a' and
# accumulated product into stack 'b'.  Initialise
# stack b with the last value read.
sb

# Turnaround function at limit of recursion: print
# accumulated 'b' value (containing b..z above).
[Lbn[ ]nq]sG

# Recursive function - on the way in, we stack up
# 'a' values and multiply up the 'b' values.  On
# the way out, we multiply up the 'a' values and
# multiply each by the corresponding 'b' value.
[dSalb*Sb
z1=G
lFx
dLb*n[ ]n
La*]dsFx

# Do the last a*b multiplication
dLb*n[ ]n

# And we have one final 'a' value that doesn't have a
# corresponding 'b':
La*n

Я предполагаю, что целочисленное сравнение z1=(которое завершает рекурсию, когда мы достигаем последнего значения) бесплатно. Это эквивалентно аналогам foreachв других языках.

Демонстрации

for i in '2 3 5' '2 3 5 7' '0 2 3 5' '0 0 1 2 3 4'
do printf '%s => ' "$i"; ./127147.dc <<<"$i"; echo
done
2 3 5 => 15 10 6
2 3 5 7 => 105 70 42 30
0 2 3 5 => 30 0 0 0
0 0 1 2 3 4 => 0 0 0 0 0 0

Демо с большими и маленькими входами:

./127147.dc <<<'.0000000000000000000542101086242752217003726400434970855712890625 1 18446744073709551616'
18446744073709551616 1.0000000000000000000000000000000000000000000000000000000000000000 .0000000000000000000542101086242752217003726400434970855712890625
Тоби Спейт
источник
1

C ++, оценка: 5990, O ([2NlogN] / 3)

Эта реализация использует таблицу поиска двоичного дерева. Моей первой реализацией была O (NlogN), но в последнюю минуту была проведена оптимизация, которая ищет произведение всех элементов массива за вычетом пары, + 2 умножения, спасших день. Я думаю, что это все еще можно оптимизировать немного дальше, может быть, еще 16% ...

Я оставил некоторые следы отладки только потому, что их легче удалить, чем переписать :)

[Edit] фактическая сложность измеряется в O ([2NlogN] / 3) для 100. На самом деле она немного хуже, чем O (NlogN) для небольших наборов, но имеет тенденцию к O ([NlogN] / 2) по мере роста массива очень большой O (0.57.NlogN) для набора из 1 миллиона элементов.

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <random>
#include <cstdlib>

using DataType = long double;

using DataVector = std::vector<DataType>;

struct ProductTree
{
    std::vector<DataVector> tree_;
    size_t ops_{ 0 };

    ProductTree(const DataVector& v) : ProductTree(v.begin(), v.end()) {}
    ProductTree(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        Build(first, last);
    }

    void Build(DataVector::const_iterator first, DataVector::const_iterator last)
    {
        tree_.emplace_back(DataVector(first, last));

        auto size = std::distance(first, last);
        for (auto n = size; n >= 2; n >>= 1)
        {
            first = tree_.back().begin();
            last = tree_.back().end();

            DataVector v;
            v.reserve(n);
            while (first != last) // steps in pairs
            {
                auto x = *(first++);
                if (first != last)
                {
                    ++ops_;
                    x *= *(first++); // could optimize this out,small gain
                }
                v.push_back(x);
            }
            tree_.emplace_back(v);
        }
    }

    // O(NlogN) implementation... 
    DataVector Prod()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            result[i] = ProductAtDepth(i, depth);
        }
        return result;
    }

    DataType ProductAtDepth(size_t index, size_t depth) 
    {
        if (depth == 0)
        {
            return ((index ^ 1) < tree_[depth].size())
                ? tree_[depth][index ^ 1]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth(index, depth - 1);
        }
        return ProductAtDepth(index, depth - 1);
    }    

    // O([3NlogN]/2) implementation... 
    DataVector Prod2()
    {
        DataVector result(tree_[0].size());
        for (size_t i = 0; i < tree_[0].size(); ++i)    // steps in pairs
        {
            auto depth = tree_.size() - 1;
            auto k = i >> depth;
            auto x = ProductAtDepth2(i, depth);
            if (i + 1 < tree_[0].size())
            {
                ops_ += 2;
                result[i + 1] = tree_[0][i] * x;
                result[i] = tree_[0][i + 1] * x;
                ++i;
            }
            else
            {
                result[i] = x;
            }
        }
        return result;
    }

    DataType ProductAtDepth2(size_t index, size_t depth)
    {
        if (depth == 1)
        {
            index = (index >> 1) ^ 1;
            return (index < tree_[depth].size())
                ? tree_[depth][index]
                : 1;
        }
        auto k = (index >> depth) ^ 1;

        if ((k < tree_[depth].size()))
        {
            ++ops_;
            return tree_[depth][k] * ProductAtDepth2(index, depth - 1);
        }
        return ProductAtDepth2(index, depth - 1);
    }

};


int main()
{
    //srand(time());

    DataVector data;
    for (int i = 0; i < 1000; ++i)
    {
        auto x = rand() & 0x3;          // avoiding overflow and zero vaolues for testing
        data.push_back((x) ? x : 1);
    }

    //for (int i = 0; i < 6; ++i)
    //{
    //  data.push_back(i + 1);
    //}

    //std::cout << "data:[";
    //for (auto val : data)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    ProductTree pt(data);
    DataVector result = pt.Prod2();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";
    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    pt.ops_ = 0;
    result = pt.Prod();

    //std::cout << "result:[";
    //for (auto val : result)
    //{
    //  std::cout << val << ",";
    //}
    //std::cout << "]\n";

    std::cout << "N = " << data.size() << " Operations :" << pt.ops_ << '\n';

    return 0;
}

Я добавляю алгоритм @ nore для полноты картины. Это действительно приятно, и это самый быстрый.

class ProductFlat
{
private:
    size_t ops_{ 0 };

    void InitTables(const DataVector& v, DataVector& left, DataVector& right)
    {
        if (v.size() < 2)
        {
            return;
        }

        left.resize(v.size() - 1);
        right.resize(v.size() - 1);

        auto l = left.begin();
        auto r = right.rbegin();
        auto ol = v.begin();
        auto or = v.rbegin();

        *l = *ol++;
        *r = *or++;
        if (ol == v.end())
        {
            return;
        }

        while (ol + 1 != v.end())
        {
            ops_ += 2;
            *l = *l++ * *ol++;
            *r = *r++ * *or++;
        }
    }

public:
    DataVector Prod(const DataVector& v)
    {
        if (v.size() < 2)
        {
            return v;
        }

        DataVector result, left, right;
        InitTables(v, left, right);

        auto l = left.begin();
        auto r = right.begin();
        result.push_back(*r++);
        while (r != right.end())
        {
            ++ops_;
            result.push_back(*l++ * *r++);
        }
        result.push_back(*l++);
        return result;
    }

    auto Ops() const
    {
        return ops_;
    }
};
Микаэль Рой
источник