Учитывая 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
вашего ответа для легкого сравнения.
+
на индексах ? Если это так, учитывается ли индексирование массива? (поскольку это все-таки синтаксический сахар для добавления и разыменования).(n-1)*n
умножениях Вы имеете в виду(n-2)*n
, не так ли?Ответы:
Python, 3 (n-2) операции, оценка = 2994
Массивы
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), что доказывает утверждение теоремы.
источник
f l = zipWith (*) (scanl (*) 1 l) (scanr (*) 1 $ tail l)
.Хаскелл , оценка 2994
Попробуйте онлайн!
Скажем, нам дали список
[a,b,c,d,e,f,g,h]
. Сначала мы сгруппируем его в пары[[a,b],[c,d],[e,f],[g,h]]
. Затем мы возвращаемся к списку половинных размеровpairs
их продуктов, чтобы получитьsubresults
Если мы возьмем первый элемент
(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
.источник
products_but_one'
может избежать этого, возвращая что-то правильной длины.1
свободное умножение. Я думаю, что отступ 1 не влияет на вещи, но я очистил свой алгоритм, чтобы не использовать их.float
.Haskell , оценка 9974
Попробуйте онлайн!
Стратегия «разделяй и властвуй», очень напоминающая сортировку слиянием. Не выполняет индексацию.
Функция
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
; если я ошибаюсь, я мог бы опустить это явно.источник
n = 1000
и посчитайте арифметические операции в коде.9974
а не к9975
умножениямn = 1000
(в случае вычисления общего продукта во внешнем слое). Включили ли вы1
во вход, который вы использовали для проверки?trace
изDebug.Trace
с броским все| trace "call!" False = undefined
настороже, я думаю. Но это используетсяunsafePerformIO
под капотом, так что это не так уж и много улучшений.Хаскелл , оценка 2994
Попробуйте онлайн!
Как это работает
Это очищенная версия алгоритма 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) г].
источник
O (n log n) операций, оценка = 9974
Работает с бинарным деревом.
питон
Это также требует операций добавления списка и некоторой арифметики для чисел, которые не являются входными значениями; не уверен, что это считается.
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
и посчитайте арифметические операции в коде.p[i] = p[i + i] * p[i + i+1]
не считаетсяn log2 n + n
операциях (это O (nlogn) между прочимp[i] = p[i + i] * p[i + i + 1]
должны быть сохранены путем оптимизации умножения. Я мог бы посчитать слишком много, однако.O ((n-2) * n) = O (n 2 ): тривиальное решение
Это просто тривиальное решение, которое умножает вместе каждое из подмножеств:
питон
Обратите внимание, что это также требует
n
операций добавления списка; не уверен, что это считается. Если это не разрешено, тоproduct(array[:index] + array[index + 1:])
можно заменить наproduct(array[:index]) * product(array[index + 1:])
, что изменяет формулу наO((n-1)*n)
.источник
product
функцииO(n)
операций? по одному на каждый элемент в массиве (хотя это можно легко изменитьO(n-1)
)Питон, 7540
Трехсторонняя стратегия слияния. Я думаю, что могу сделать даже лучше, чем это, с еще большим слиянием. Это O (n log n).
РЕДАКТИРОВАТЬ: Исправлена ошибка.
Соответствующая функция
missing_products
, которая дает общий продукт и все из них с отсутствующим элементом.источник
tri_merge
? Кроме того, вы можете заменить2 * split_size + ...
вtri_partition
сsplit_size + split_size + ...
.DC, оценка 2994
Я предполагаю, что целочисленное сравнение
z1=
(которое завершает рекурсию, когда мы достигаем последнего значения) бесплатно. Это эквивалентно аналогамforeach
в других языках.Демонстрации
Демо с большими и маленькими входами:
источник
C ++, оценка: 5990, O ([2NlogN] / 3)
Эта реализация использует таблицу поиска двоичного дерева. Моей первой реализацией была O (NlogN), но в последнюю минуту была проведена оптимизация, которая ищет произведение всех элементов массива за вычетом пары, + 2 умножения, спасших день. Я думаю, что это все еще можно оптимизировать немного дальше, может быть, еще 16% ...
Я оставил некоторые следы отладки только потому, что их легче удалить, чем переписать :)
[Edit] фактическая сложность измеряется в O ([2NlogN] / 3) для 100. На самом деле она немного хуже, чем O (NlogN) для небольших наборов, но имеет тенденцию к O ([NlogN] / 2) по мере роста массива очень большой O (0.57.NlogN) для набора из 1 миллиона элементов.
Я добавляю алгоритм @ nore для полноты картины. Это действительно приятно, и это самый быстрый.
источник