Я проводил некоторые исследования и обнаружил некоторые алгоритмы, которые имеют время выполнения больше 0(N).Мне любопытно, если кто-нибудь знает о линейном алгоритме времени для нахождения наибольшего общего делителя?
0(N)
Если есть, никто еще не нашел его; из Википедии ;
самый известный детерминированный алгоритм Чора и Голдрайха, который (в модели CRCW-PRAM) может решить проблему за O (n / log n) с n1 + ε процессоров.