Big O обозначения и алгоритмы

Question

Я сейчас учусь и пытаюсь реализовать некоторые алгоритмы.Я пытаюсь понять нотацию Big O и не могу понять сложность Big O для приведенного ниже алгоритма:

while (a != 0 && b != 0)
{
    if (a > b)
        a %= b;
    else
        b %= a;
}

if (a == 0)
    common=b;
else
    common=a;

Answer 1

Легко видеть, что после двух итераций наименьшее из чисел становится как минимум вдвое меньше.Если в начале он был равен m, то после 2K итераций он будет не более m / 2 ^ K.Если мы поместим здесь K = [log_2 (m)] + 1, мы увидим, что после 2K итераций наименьшее из чисел становится равным нулю, и цикл завершается.Следовательно, число итераций не более 2 (log_2 m + 1) = O (log m).

Answer 2

Это евклидов алгоритм для вычисления наибольшего общего делителя двух целых чисел. Я предоставлю вам исследование сложности этого алгоритма, но числа Фибоначчи играют важную роль.

Answer 3

Большинству людей (которые не являются математиками) никогда не нужно узнавать это, это уже задокументировано: http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency