Какова временная сложность алгоритма Евклида (верхняя граница, нижняя граница и среднее значение)?

Чтобы решить некоторые предварительные вопросы, позвольте$T(a,b)$— количество шагов, предпринятых в алгоритме Евклида, который многократно оценивает$\gcd(a,b)=\gcd(b,a\bmod b)$до$b=0$, предполагая$a\geq b$. Кроме того, пусть$h=\log_{10}b$быть количеством цифр в$b$(дай или возьми). (Заметим, что в этих расчетах при подсчете шагов мы игнорируем вопрос о временной сложности$\mathrm{mod}$функция. Если мы предположим, что это$O(1)$, то все нижеследующее относится и к временной сложности алгоритма.

1. В худшем случае, как вы сказали,$a=F_{n+1}$и$b=F_n$, где$F_n$это последовательность Фибоначчи, так как она будет вычислять$\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1})$пока не дойдет до$n=0$, так$T(F_{n+1},F_n)=\Theta(n)$и$T(a,F_n)=O(n)$. С$F_n=\Theta(\varphi^n)$, это означает, что$T(a,b)=O(\log_\varphi b)$. Обратите внимание, что$h\approx log_{10}b$и$\log_bx={\log x\over\log b}$подразумевает$\log_bx=O(\log x)$для любого$a$, поэтому наихудшим случаем для алгоритма Евклида является$O(\log_\varphi b)=O(h)=O(\log b)$.

2. Средний случай требует немного больше внимания, так как он зависит от вероятностной ситуации. Для того, чтобы точно рассчитать его, нам нужно распределение вероятностей. Если$a$фиксируется и$b$выбирается равномерно из$\mathbb Z\cap[0,a)$, то количество шагов$T(a)$является

   $$T(a)=-\frac12+6\frac{\log2}\pi(4\gamma-24\pi^2\zeta'(2)+3\log2-2)+{12\over\pi^2}\log2\log a+O(a^{-1/6+\epsilon}),$$

   или, для меньшей точности,$T(a)={12\over\pi^2}\log2\log a+O(1)$. (Источник: Википедия)

3. В лучшем случае,$a=b$или$b=0$или какой-либо другой удобный случай, подобный этому, поэтому алгоритм завершается за один шаг. Таким образом,$T(a,a)=O(1)$.

Если мы работаем на компьютере, используя 32-битные или 64-битные вычисления, как это обычно бывает, то отдельные$\bmod$операции на самом деле выполняются за постоянное время, поэтому эти оценки верны. Если же мы делаем вычисления с произвольной точностью, то для оценки фактической временной сложности алгоритма нам нужно использовать это$\bmod$имеет временную сложность$O(\log a\log b)$. В этом случае вся «работа» выполняется на первом шаге, а остальные вычисления также$O(\log a\log b)$, поэтому сумма$O(\log a\log b)$. Однако я хочу подчеркнуть, что это применимо только в том случае, если число настолько велико , что вам нужна произвольная точность для его вычисления.

(Это подчеркивает разницу между нотацией «большой О» математика и нотации «большой О» программиста: в первом случае вы хотите, чтобы оценка была истинной.$\forall n$, даже те$n$которые настолько абсурдно велики, что никто никогда не сможет их записать или сохранить в памяти, тогда как во втором случае программистов в первую очередь интересуют$n\in[0,2^{64}]$, и это либеральная оценка. Для них важнее увидеть «ведущий вклад» во временную сложность, а для алгоритма Евклида меньшее число определяет сложность вычислений в целом.)

время выполнения является линейным в представлении большего числа: если$a\ge b$тогда время выполнения$O(\log(a))$