Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления наибольшего общего делителя двух целых чисел:int gcd(int m, int n) { // дано: целые числа m, n, хотя бы одно отлично от нуля // надо: вычислить НОД пары (m, n) int a = m, b = n; while (b != 0) { // Invariant: НОД(a, b) == НОД(m, n) int r := a % b; // находим остаток от деления a на b a = b; b = r; // заменяем пару (a, b) на (b, r) } return a; // ответ = a}
(Отметьте один правильный вариант ответа.)
Варианты ответа
Время работы не больше, чем C*max(m, n), где C - некоторая константа (т.е. время пропорционально максимальному из чисел m, n).
Время работы не больше, чем C*log2max(m, n), где C - некоторая константа (т.е. время пропорционально количеству цифр в двоичной или десятичной записи максимального из чисел m, n). (Верный ответ)
Время работы не больше, чем C*r, где C - некоторая константа, r - квадратный корень из max(m, n) (т.е. время пропорционально квадратному корню из максимального числа).