Почему рекурсивный Евклид для НОД работает за O(log) и сколько шагов в худшем случае?
Алгоритм Евклида я использую, но не понимаю, почему он такой быстрый. Почему число шагов логарифмическое, а не линейное? И правда ли, что худший случай — это соседние числа Фибоначчи?
2 ответа
Ключевое наблюдение: за два шага Евклида большее число уменьшается минимум вдвое. Покажем это. Шаг Евклида заменяет (a, b) на (b, a mod b) при a ≥ b. Утверждение: a mod b < a / 2. Действительно — если b ≤ a/2, то a mod b < b ≤ a/2; если b > a/2, то a mod b = a − b < a/2. В любом случае через один шаг остаток меньше a/2.
Значит большее из чисел падает вдвое за O(1) шагов, и всего шагов O(log min(a, b)). Поскольку числа до ~10^18 (60 бит), это максимум порядка ~90 итераций — практически мгновенно.
long long gcd(long long a, long long b) {
while (b) { a %= b; swap(a, b); }
return a; // итеративно, без риска переполнения стека
}
Итеративная версия предпочтительнее рекурсивной на больших данных — нет накладных расходов на стек вызовов (хотя глубина и так логарифмическая).
Да, худший случай Евклида — соседние числа Фибоначчи. Для пары (F_{n+1}, F_n) каждый шаг даёт ровно (F_n, F_{n-1}) (потому что F_{n+1} mod F_n = F_{n-1}), то есть индекс падает на 1 за шаг — максимально медленно. Число шагов тогда ≈ n, а так как F_n ≈ φ^n (φ — золотое сечение), получаем n ≈ log_φ(a). Это и есть теорема Ламе: количество шагов Евклида не превышает примерно 5·(число десятичных цифр меньшего числа). То есть даже худший случай — логарифмический.