А
Эм... Хз. Я кнута не читал еще.
Size: a a a
2021 May 05
С
да ему Timsort нужен. Я уже дал и описание и алгоритм и реализацию на С++ в соседнем чате.
K
понял, спасибо
K
да, ещё раз, благодарен
DK
Товарищи, есть быстрый способ нахождения НОД в большом массива чисел?
EZ
O(n*log(max)) либо O(n*log(n)*log(min)) тупо с алгоритмом евклида недостаточно быстро?
IB
Можно распараллелить.
NK
делишь массив на N частей, считаешь НОД в каждой части в отдельном потоке и потом считаешь НОД для каждой из результатов
K
parallelStream юзайте, он сам умный
K
IntStream.range(0, arr.length).parallel().map(i->arr[i]).reduce((i,j)->gcd(i,j)).getAsInt();
NK
ну если на жабе писать да
K
простите, был в интернет-детоксе, опять забыл о существовании плюсов
p
НОД считается за O(n+log(C))
p
Если каждый раз ans=gcd(ans,a[i]) делать
K
тоже хорошо
K
а ограничения на размер числа есть?
p
C-ограничение на a[i]
K
на google foobar была задача, один из подходов к решению которой сдавался только если оптимизировать вычисление gcd
p
Не Евклида писать?