Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, infused, Вы писали:
I>> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...
I>>Предпологаю что это порядка log2(max(m,n))... ???
I>>Зараннее спасибо.
К>При желании — можно выйти в O(1), точнее — в ноль 
К>К>int gcd(int a, int b)
К>{
К> a = abs(a);
К> b = abs(b);
К> while(a > 1 && b > 1) // можно while(a != 0 && b != 0) -- но это неоптимально
К> if(a > b)
К> a -= b;
К> else
К> b -= a;
К> if(a == 1 || b == 1)
К> return 1;
К> else
К> return a + b; // одно из них == 0
К>}
К>
Да алгоритм на разности мне знаком.... Вопрос в количестве операций (макс. количестве)!
Сколько их при делении... и сколько их(операций) например в данном случае при вычитании...
