Итак, посмотрим.Общий метод поиска GCD массива чисел:
result = a[0]
for i = 1 to length(a)-1
result = gcd(result, a[i])
Так в чем же сложность алгоритма gcd?Ну, это довольно сложный вопрос.См., Например, Временная сложность алгоритма Евклида
Если мы сделаем вид, как положено в принятом ответе, что алгоритм GCD имеет постоянное время (т. Е. O (1)), тосложность цикла выше O (n).Это разумное предположение для чисел, которые вписываются в компьютерные регистры.И если это так, то потратить O (n log n) время на сортировку массива почти наверняка будет проигрыш.
Но в действительности вычисление GCD является линейным по количеству цифр в двух числах.Если ваши входные данные состоят из большого числа больших чисел, возможно , что сортировка массива в первую очередь даст вам преимущество.Причина в том, что результат gcd(a, b) по определению даст вам число, которое не больше, чем min(a,b).Таким образом, сначала получая GCD из двух наименьших чисел, вы ограничиваете количество цифр, с которыми вам приходится иметь дело.Преодолеет ли это ограничение стоимость сортировки массива, неясно.
Если числа больше, чем вписываются в компьютерный регистр (сотни цифр), то вычисление GCD обходится дороже.Но, опять же, сортировка тоже.
Итак, ответ на ваш вопрос заключается в том, что сортировка почти наверняка увеличит скорость вычисления GCD массива чисел, но будет ли повышение производительности компенсировать стоимость сортировкинеясно.
Я думаю, что единственный способ узнать наверняка - это проверить его на репрезентативных данных.